FRAKTAL - konkurs programistyczny

Zadanie polega na wyznaczeniu ilosci różnych liczb Fibonacciego mieszczących się w przedziale [a..b].

Wejście

W pierwszym wierszu niewielka liczba t określająca liczbę zestawów danych.

Każdy zestaw danych składa się z dwóch liczby całkowitych a i b takich, że 1 ≤ a ≤ b ≤ 10⁹.

Wyjście

Dla każdeog zestawu jedna liczba określająca ilość różnych liczb Fibonacciego znajdujących się w przedziale [a..b].

Przykład

Wejście:
4
1 3
4 7
8 8
1000000 1000000000

Wyjście:
3
1
1
14