fibsmen

Fibsmen

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

Poveste şi cerinţă...

Fiind dat un numar natural $N$ sa se spuna in cate moduri se poate scrie ca suma de termeni distincti din sirul lui Fibonacci. Pentru fiecare mod posibil nu va conta ordinea in care se vor aduna termenii. Mai precis, doua moduri care contin exact aceeasi termeni nu se vor considera distincte si in consecinta se vor numara o singura data.
 
Sa se raspunda la $Q$ astfel de intrebari .

h2. Date de intrare

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

Fişierul de intrare $fibsmen.in$ contine pe prima linie o singura valoare $Q$ cu semnificatia de mai sus.
Pe fiecare din urmatoarele $Q$ linii se afla un singur numar natural $N$ care va reprezinta valoarea la care trebuie sa se raspunde pentru intrebarea respectiva

h2. Date de ieşire

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

În fişierul de ieşire $fibsmen.out$ se vor afisa exact $Q$ linii. Pe a $i$-a linie se va afla raspunsul pentru a $i$-a intrebare din fisierul de intrare.

h2. Restricţii

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

* $1 ≤ Q ≤ 200 000$
* $1 ≤ N ≤ 10^16^$

h2. Exemplu
table(example). |_. fibsmen.in |_. fibsmen.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 3
  6
  73
  666013
| 2
  6
  340

|
h3. Explicaţie

...

Cele $2$ moduri distincte in care se poate scrie numarul $6$ sunt: $1+2+3$ si $1+5$.
Cele $6$ moduri distincte in care se poate scrie numarul $73$ sunt: $2+3+13+21+34$, $2+3+5+8+21+34$, $5+13+21+34$, $2+3+13+55$, $2+3+5+8+55$ si $5+13+55$.

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

9812