Consideram sirul format in modul urmator:
- initial sirul este "1";
- la fiecare pas, se aplica asupra sirului urmatoarele transformari: "1" -> "10" si "0" -> "1".
Dupa un numar infinit de aplicari ale acestor transformari obtinem sirul "1011010110110101101...".
Se pun Q intrebari de forma: cate cifre 1 exista intre pozitiile a si b ?

Pe prima linie a fisierului de intrare infinit.in se afla numarul Q. Urmatoarele Q linii contin cate o pereche de numere a, b separate prin cate un spatiu.

In fisierul infinit.out se vor afisa Q linii, pe linia i aflandu-se raspunsul pentru perechea (a, b) de pe a (i+1)-a linie din fisierul de intrare.

• 1 <= Q <= 5000
• 1 <= a <= b < 2⁶³
  

infinit.in	infinit.out
1 2 8	4

Timp maxim de executie/test: 0.1 secunde

Tiberiu-Lucian Florea
Universitatea Bucuresti, Facultatea de Matematica si Informatica
Contact: tiberiu.florea@gmail.com