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 6^th 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<=10¹⁸). 

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