Toată lumea ştie că Fibocel este pasionat de numere şi că vrea să iasă în evidenţă cu orice preţ. Într-o zi, el s-a decis să numească un număr fibocel (după numele lui) dacă numărul de biţi egali cu 1 din reprezentarea binară a numărului este un număr Fibonacci.

Cum asta nu e de ajuns pentru el, Fibocel s-a decis să propună şi o problemă la concursul lui preferat de la Iaşi.

Cerința

Să se raspundă la Q întrebări de forma: Câte numere fibocel există în intervalul închis [A, B]?

Date de intrare

Fișierul de intrare fibocel.in conține pe prima linie numărul natural Q, iar pe următoarele Q linii se găsesc câte două numere naturale A şi B separate prin exact un spaţiu, reprezentând extremităţile intervalului la care se referă întrebarea.

Date de ieșire

Fișierul de ieșire fibocel.out va conține exact Q numere, câte unul pe o linie, reprezentând răspunsurile la cele Q întrebări, în ordinea în care ele apar în fişierul de intrare.

Restricții și precizări

• 1 ≤ Q ≤ 50.000
• 1 ≤ A ≤ B ≤ 1015
• Şirul Fibonacci se defineşte astfel: \(F_0 =F_1 =1; F_n =F_{n-1} +F_{n-2} \), pentru \(n ≥ 2\)
• Pentru 40% din teste B ≤ 1.000.000

Exemplul 1

fibocel.in

1
15 16

fibocel.out

1

Explicație

15(10) =1111(2) nu este fibocel (are 4 biţi de 1 iar 4 nu este număr Fibonacci)
16(10) =10000(2) este fibocel (are 1 bit de 1 iar 1 este număr Fibonacci)

Exemplul 2

fibocel.in

7
1 13
13 31
13 131
31 131
131 313
313 1313
1313 3131

fibocel.out

13
14
76
63
97
421
667