God of Number Theory

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 32768/32768 K (Java/Others)

Description

In ACM_DIY, there is one master called “AekdyCoin”. As we know, he is the god of “Number Theory”. He always kills the problem about “Number Theory” in seconds! But of course we do not have any idea about these problems~ One day in ACM_DIY, AekdyCoin asks us one problem:
You are given three non-negative integers A, B and K, you are expected to find how many X that satisfy.
X^A = B( mod (2K + 1) )
X is in the ranger [0, 2K];

Of course we have no idea about this problem, so could you help us?

Input

The first line is one integer T indicates the number of the test cases. (T <= 1000)
Then for every case, only one line contains three integers A, B and K. (1 <= A, B <= 10^9, 1 <= K <= 5 * 10^8)

Output

Output the answer in a single line.

Sample Input

3 1 1 1 11 11 11 111 111 111

Sample Output

1 0 0

Hint

notonlysuccess

Source

ACMDIY第二届群赛

提交代码