Dãy số \(Fibonacii\) được định nghĩa như sau:

\(F_1=1;F_2=1;F_i=F_{i-1}+F_{i-2} (i≥3).\)

Dãy các số \(Fibonacii\) đầu tiên: \(1, 1, 2, 3, 5, 8, 13, …\)

Yêu cầu: Cho 2 số nguyên dương \(l\), \(r\). Đếm số lượng các số \(Fibonacii\) trong đoạn \([l,r].\)

Dữ liệu Vào từ file văn bản FIBLR.INP có cấu trúc:

• Dòng đầu tiên chứa số nguyên dương \(t(1≤t≤10^5)\)

• \(t\) dòng tiếp theo, mỗi dòng chứa hai số nguyên dương \(l, r(1≤l≤r≤10^{18}).\)

Kết quả ghi vào file văn bản FIBLR.OUT có cấu trúc:

• Ghi \(t\) dòng, mỗi dòng ghi một số nguyên là kết quả tìm được của test tương ứng.

Ràng buộc

• Subtask 1: \(l≤r≤10^6\)

• Subtask 2: \(l≤r≤10^{18}\)

SAmple Input

1
1 10

Sample Output

5