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 ?

Scrieti un program care sa raspunda la cele Q intrebari.

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⁶³
  

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