Fişierul intrare/ieşire:	fibsmen.in, fibsmen.out	Sursă	Infoarena Monthly 2014, Runda 4
Autor	Andrei Cristian Lambru	Adăugată de	Cristian Lambru •maritim
Timp execuţie pe test	0.25 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Fibsmen

Fiind dat un numar natural N sa se spuna in cate modurile se poate scrie ca suma de termeni distincti din sirul lui Fibonacci. Nu conteaza ordinea in care se aduna termenii. De exemplu: 6 se poate scrie in doua moduri: 1+2+3 si 1+5. 

Sa se raspunda la Q astfel de intrebari .

Date de intrare

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 reprezinta valoarea la care trebuie sa se raspunde pentru intrebarea respectiva 

Date de ieşire

Î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.

Restricţii

• 1 ≤ Q ≤ 200 000
• 1 ≤ N ≤ 10¹⁶

Exemplu

Explicaţie

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
• 5+13+55

Cum se trimit solutii?