DIVFIBS - Divisible Fibonacci Numbers

In mathematics, the Fibonacci sequence is calculated by adding the previous two members of the sequence. The first few Fibonacci numbers are

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...

Considering the indices start from 1 the 6th Fibonacci number in this sequence is 8 and is divisible by 1, 2, 4 and 8. You are given two indices L and R (L<=R) of this sequence and you have to calculate how many Fibonacci numbers are divisible by M in range [L, R] inclusive.

Input

Input begins with a line containing a single integer T (1<=T<=500), denoting the number of test cases. T test cases follow. Each test case begins with a line containing three integers L R (1<=L<=R<=100000) and M (1<=M<=1018)

Output

For each test case, output a single line containing the answer as an integer.

Example

Input:
3
6 6 4
4 18 5
1 10 3

Output:
1
3
2

Added by:imranziad
Date:2015-12-08
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY

hide comments
2016-07-16 21:46:33 Francky
This one should be put in tutorial section...
==
Try http://www.spoj.com/problems/DIVFIBS2/ : Brute force will not pass !!! ;-)


Last edit: 2016-07-16 21:47:53
2016-07-16 08:35:25 Piyush Kumar
O! Brute Force passes :) !
2016-07-01 14:48:55
finally removed this from my to-do list after 6 months.really nice problem.. <3
2016-02-28 22:16:15 abhi
wrong answer is because of overflow. Take mod and then store the numbers
2015-12-20 00:02:09 kp
check for
1
2 2 1
ans : 1
2015-12-19 21:39:09 priyank
nice one
2015-12-12 15:01:14 mehmetin
Problem could be changed to have harder constraints, then rejudged (maybe something like T = 5000)

Last edit: 2015-12-12 15:06:40
2015-12-11 04:27:26 :.Mohib.:
Unable to figure out why getting WA, @admin please check my code where I am failing??
2015-12-10 08:33:23 shadowfax
@Prakhar Dev Gupta can't find your source code :( I'd say try to simulate for larger fib numbers like 100th.
2015-12-10 08:18:54 shadowfax
@Lakshman please check case: L=6, R=9, M=2. The answer should be 2.

Last edit: 2015-12-10 08:51:43
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.