fibocel

Fibocel

== include(page="template/taskheader" task_id="fibocel") ==

Poveste şi cerinţă...

Toata 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.
 
h2. Cerinţă
 
Să se raspundă la {*Q*} întrebări de forma: Câte numere fibocel există în intervalul închis {*[A, B]*} ?

h2. Date de intrare

Fişierul de intrare $fibocel.in$ ...

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.

h2. Date de ieşire

În fişierul de ieşire $fibocel.out$ ...

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.

h2. Restricţii

* $... ≤ ... ≤ ...$

* 1 ≤ {*Q*} ≤ 50.000
* 1 ≤ {*A*} ≤ {*B*} ≤ 10^15^
* Ş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

h2. Exemplu
table(example). |_. fibocel.in |_. fibocel.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|
 
h3. Explicaţie

h2. Exemplu

...

table(example). |_. fibocel.in |_. fibocel.out |_. Explicaţie |
| 1
15 16
| 1
| 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)
|
| 7
1 13
13 31
13 131
31 131
131 313
313 1313
1313 3131
| 13
14
76
63
97
421
667
| .
|

== include(page="template/taskfooter" task_id="fibocel") ==