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 n >= 3

Đề 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 <= T <= 10⁶).

T dòng tiếp theo mỗi dòng gồm 2 số nguyên dương L, R (L <= R <= 10⁶)

OUTPUT:

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