21488_BoardGameDice

hh is a Board Game hobbyist, he often plays Board Game such as Catan, Carcassonne, The Werewolves, A song of ice and fire with friends.

To play the games, we need some dices, and these dices are very unusual. Maybe with eight or twelve sides.

hh plays with N friends today (including himself). They'll choose one person to be the judge. But the problem is: there is only a M-sided dice. How to pick a judge with the dice, so that everyone has equal probability of being chosen (the probability should always be 1 / N)?

hh has an idea here:

1) Get  x

Decide rolling the dice x times to make M ^x larger than or equal to N.

2) Players choose sequences

Each player chooses a sequence with x elements (1~M).

For example, a 6-sides dice and x equal to 3, hh will gets sequence 4 5 6. Players' sequences should be different from each other.

3) Pick the judge

Roll the dice for x times, we can get a result sequence, if someone has the same sequence as the result, he will be the judge; otherwise, repeat 1)-3), until the judge is chosen.

It's a bigger project, hh wants know the expected number of times we will need to throw dice to determine the judge.

The first line is a number T ( 1 ≤ T ≤ 30 ), which represents the number of cases. The next T blocks following are the cases.

Each case contains two integer N , M ( 2 ≤ N ≤ 10⁹, 2 ≤ M ≤ 20 )

For each case, output the number of case and expected number of throw as an irreducible fraction in the following form: "a/b" (as shown in the sample output)

2
3 2
9 3

Case 1: 8/3
Case 2: 2/1