In ACM_DIY, there is one master called “ShaZai”. 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, ShaZai asks us one problem:

You are given three non-negative integers A, B and K, you are expected to find the number of numbers that satisfy:

1. X^A = B (mod (2K + 1))
2. X is in the range [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.

Example

Input:
3
213 46290770 80175784
3 46290770 80175784
3333 46290770 80175784

Output:
27
27
297