Bicycle Puzzle#1195
Per and Gunnar found a wonderful online bicycle picture puzzle. Since they are both competitive, they decided to find out who is better at solving it. The goal of the game is to assemble the picture of the bicycle. At the start of each game, the picture is divided into W \times H equal rectangles and scrambled randomly. The player repeatedly selects any two rectangles and swaps them. This process continues until the picture is correctly assembled. The score for the game is the number of swaps performed.
After Gunnar has played the game, he sends his score (together with and ) to Per, and challenges him to beat the score. Per soon realizes that if he is unlucky with the scrambling, it is impossible to beat Gunnar's score.
Per quickly writes a program to calculate the probability that he can beat Gunnar's score (assuming all scrambled pictures are equally likely) when playing optimally. However, he is not sure if his program is correct and asks you to write the same program.
The first line contains the number of test cases (0 < T \leq 150). Each test case consists of a line with three integers (0 < W \leq 5), (0 < H \leq 4), and (0 \leq S \leq W \cdot H), where is Gunnar's final score. When comparing two scores, the smaller one is considered better.
For each test case, output on a separate line the probability that Per can beat Gunnar's score. Print the probability as an irreducible fraction where the numerator and denominator are separated by a / character. If the answer is an integer, print only the numerator.
Example 1