Định nghĩa số Fibnacci thứ ~n~ (ký hiệu là ~F_n~) bằng công thức truy hồi sau:

• ~F_0 = 0~

• ~F_1 = 1~

• ~F_i = F_{i - 1} + F_{i - 2}~

Nói cách khác, số Fibonacci thứ ~n~ bằng tổng hai số fibonacci liền kề trước nó. Dưới đây là một vài số Fibonacci đầu tiên:

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

Chu kỳ Pisano thứ ~n~ (ký hiệu là ~\pi(n)~) là độ dài của chu kỳ ngắn nhất của dãy Fibonacci lấy modulo của ~n~.

Ví dụ: Dãy Fibonacci lấy modulo của ~3~ là ~0, 1, 1, 2, 0, 2, 2, 1, 0, 1, 1, 2, 0, 2, 2, 1, 0, 1, 1, 2, 0, 2, 2, 1, 0, ...~ Ta có thể thấy rằng dãy này được lặp theo chu kỳ ~[0, 1, 1, 2, 0, 2, 2, 1]~. Vì vậy, ~\pi(3) = 8~.

Cho ~q~ truy vấn, xử lý các truy vấn như sau:

Với mỗi truy vấn, cho ~3~ số ~l, r, k~. Nhiệm vụ của bạn là đếm xem có bao nhiêu số ~x~ thỏa mãn ~l \leq x \leq r~ và ~\pi(x) = k~.

Input

• Dòng đầu tiên chứa một số nguyên dương ~q~ ~(q \leq 10^5)~.
• ~q~ dòng sau, mỗi dòng chứa ~3~ số nguyên dương ~l, r, k~ ~(l, r \leq 10^{18}, k \leq 200)~.

Output

• Gồm ~q~ dòng, dòng thứ ~i~ thể hiện cho truy vấn thứ ~i~.

Sample Input

4
1 1 1
3 3 8
1 1000 100 
1 10 4

Sample Output

1
1
4
0

Scoring