Đị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\le x\le r$ và $\pi (x)=k$.

Input

• Dòng đầu tiên chứa một số nguyên dương $q$ $(q\le {10}^5)$.
• $q$ dòng sau, mỗi dòng chứa $3$ số nguyên dương $l,r,k$ $(l,r\le {10}^{18},k\le 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