Dãy Fibonacci là dãy vô hạn các số tự nhiên bắt đầu bằng hai phần tử ~1~ và ~1~, các phần tử sau đó được thiết lập theo quy tắc mỗi phần tử luôn bằng tổng hai phần tử trước nó.

~F(1) = F(2) = 1~

~F(n) = F(n - 1) + F(n - 2)~ với ~(3 \le n)~

Đề bài: Cho ~2~ số ~L, R~. Tìm số lượng số Fibonacci trong đoạn từ ~L~ đến ~R~.

Input

• Dòng đầu chứa số nguyên ~T~ thể hiện số testcase ~(1 \le T \le 10^6)~.,
• ~T~ dòng tiếp theo mỗi dòng gồm ~2~ số nguyên dương ~L, R~ ~(L \le R \le 10^6)~.

Output

• In ra ~T~ dòng. Mỗi dòng là số lượng số Fibonacci tương ứng với testcase thứ ~T~.

Scoring

• Không có giới hạn gì thêm

Ví dụ

Input

2
1 10
2 5

Output

6
3