You are given an equation in x and y variables of the form xp + x + yq = K. You are required to find out the total number of possible non-negative integral solutions for this equation given p, q and K as input. A solution is a pair of non-negative integers (x, y) that satisfies the above equation.
Input Format :
The first line of the input gives the number of test cases, T. T test cases follow. Each test case starts with one line with three integers: p, q and K.
Output Format:
For each test case, output one line containing "Case #x:", where x is the test case number (starting from 1). Then, for every test case, output the number of solutions to the equation satisfying the constraints.
Constraints:
p, q and K are positive integers.
0 < T <= 20
2 <= p, q <= 10
0 < K <= 1014
For the first test-case, the equation is x2 + x + y2 = 4. x=0, y=2 is the only possible solution satisfying the constraints.
For the second test-case, the equation is x2 + x + y2 = 2016. There are two possible solutions where x and y are non-negative integers: x=31, y=32 and x=44, y=6.
