The Fibonacci sequence is defined by : f_n = n for n < 2, and f_n = f_n-1 + f_n-2 for n > 1.
f = (0, 1, 1, 2, 3, 5, 8, ...)

You have to count how many terms are divisible by a given integer in the beginning of the sequence.

Input

The first line of input contains one integer: T the number of test cases.
On each of the next T lines, your are given three integers: a, b, and k.

Output

For each test case, you have to print the number of term f_n that are divisible by k, for n in [0..a^b].
As the result may be a big number, simply output your result modulo 10⁹+7

Example

Input:
3
3 2 3
2 3 8
9 1 6


Output:
3
2
1

Explanation: For the first case, a^b = 3² = 9, and the terms with rank 0 to 9 are : 0, 1, 1, 2, 3, 5, 8, 13, 21, 34.
There are 3 numbers divisible by k=3.

Constraints

0 < T < 10^4
0 < a < 10^18
0 < b < 10^18
1 < k < 10^18

To give more interest in the best part of the problem, you can assume that the maximum prime factor of k is less than or equal to 10⁶.
Time limit is approx 4x the time for my 1.4kB PY3.4 submission (based on my old code for problem ??? you should find).
Good luck, and have fun ;-)

Edit(2017-02-11) : New time limit (after compiler changes).