DIVFIBS - Divisible Fibonacci Numbers

no tags 

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

hide comments
Francky: 2016-07-16 21:46:33

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
Piyush Kumar: 2016-07-16 08:35:25

O! Brute Force passes :) !

azam_9: 2016-07-01 14:48:55

finally removed this from my to-do list after 6 months.really nice problem.. <3

abhi: 2016-02-28 22:16:15

wrong answer is because of overflow. Take mod and then store the numbers

kp: 2015-12-20 00:02:09

check for
1
2 2 1
ans : 1

priyank: 2015-12-19 21:39:09

nice one

mehmetin: 2015-12-12 15:01:14

Problem could be changed to have harder constraints, then rejudged (maybe something like T = 5000)

Last edit: 2015-12-12 15:06:40
:.Mohib.:: 2015-12-11 04:27:26

Unable to figure out why getting WA, @admin please check my code where I am failing??

shadowfax: 2015-12-10 08:33:23

@Prakhar Dev Gupta can't find your source code :( I'd say try to simulate for larger fib numbers like 100th.

shadowfax: 2015-12-10 08:18:54

@Lakshman please check case: L=6, R=9, M=2. The answer should be 2.

Last edit: 2015-12-10 08:51:43

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