Board Game Dice

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. x is the smallest integer 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 [5 4 6]. Players' sequences should be different from each other.(such as [6 4 5] is different from [5 4 6])

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<=100), 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 rolling 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

NotOnlySuccess

2011 Alibaba Programming Contest