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).


hide comments
[Lakshman]: 2016-07-30 11:03:33

@Francky can you Please tell me if my approach is correct ?
Thanks.

=(Francky)=> Your approach is correct, you have WA only on some big input. I didn't search the reason in your code. Good luck for debug, or corner case search...
Edit : sorry, it's not for the big input file you have WA, you have WA only for small one. I've inverted them here : first the big one, and then the small ; sorry again. Good luck for debug. (very small input).

(Lakshman)=>Thank you very much @Francky

=(Francky)=> You're welcome ;-)

Last edit: 2016-07-31 15:28:24

Added by:Francky
Date:2016-07-16
Time limit:1s-15s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY
Resource:DIVFIBS