Problem E: Casino Advantage

Several casinos in the Atlantic City are contemplating a new game to attract gamblers. In this game, a ball is rolled randomly into a roulette wheel partitioned into N slots (labelled 1, 2, ..., N). The label of the slot in which the ball lands is the result of the roll. The ball is then removed and another ball is rolled. A total of m balls are rolled.

The players make bets on the number of distinct numbers (K) appearing during the m rolls. The casinos wish to set the payout ratios for winning bets, such that the casinos will have a slight advantage over the gamblers. In particular, they need to know the probability of a bet being the winning bet. They have hired the Altantic City Mathematicians (ACM) to help them with this problem: given values of N, M and K (1 <= N,M,K <= 10), compute the probability that K distinct values will appear when M balls are rolled into the roulette wheel with N slots. It is assumed that each roll is independent of the others, and each of the N results are equally likely for each roll.

Input Format

The input starts with an integer T - the number of test cases (T <= 1000). T cases follow on each subsequent line, each of them containing 3 integers - N, M and K.

Output Format

For each case, print the probability as a reduced fraction, following the format of the sample output. That is, print the probability in the form A/B where A and B have no common factors. If the probability is 0 or 1, just print the integer. A and B are guaranteed to fit into a signed 32-bit integer.

Sample Input

4
3 1 2
2 5 2
3 5 3
4 6 2

Sample Output

0
15/16
50/81
93/1024

Howard Cheng
ACPC 2011