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?
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 the answer in a single line.