You are given an equation in x and y variables of the form x^p + x + y^q = 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 ≤ 10^14

SAMPLE INPUT
2
2 2 4
2 2 2016

SAMPLE OUTPUT
Case #1: 1
Case #2: 2

Explanation

For the first test-case, the equation is x^2 + x + y^2 = 4. x=0, y=2 is the only possible solution satisfying the constraints.

For the second test-case, the equation is x^2 + x + y^2 = 2016. There are two possible solutions where x and y are non-negative integers: x=31, y=32 and x=44, y=6.

见题面

见题面