## DIVFIBS2 - Divisible Fibonacci Numbers

no tags

The Fibonacci sequence is defined by : fn = n for n < 2, and fn = fn-1 + fn-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 fn that are divisible by k, for n in [0..ab].
As the result may be a big number, simply output your result modulo 109+7

### Example

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

Output:
3
2
1
```

Explanation: For the first case, ab = 32 = 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 106.
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).