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

Poveste şi cerinţă...

Toti studentii ONIS cunosc reprezentarea in baza 2 a numerelor intregi. In aceasta problema, vom incepe cu numarul "1" in baza 2 pe care il scriem astfel:
 
1
 
Observam ca mai sus am scris un '1' asa ca la pasul urmator vom scrie:
 
1 1 (un '1')
 
Acum avem scris doi de '1' iar doi este '10' in baza 2, astfel ca vom scrie:
 
1 0 1 (doi de '1')
 
Citind randul anterior observam un '1', un '0' si inca un '1', deci obtinem:
 
1 1 1 0 1 1
 
Si putem continua astfel:
 
1 0 0 1 1 0 1 1 1 0 1 1
 
1 1 1 0 0 1 0 1 1 0 1 1 1 1 0 1 0 1
...
 
Problema cere sa calculati numarul de cifre binare necesare in al N-lea element al secventei.

h2. Date de intrare

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

Fişierul de intrare $blas.in$ contine pe prima linie numarul de teste T. Urmatoarele T teste contin diferite valori pentru N.

h2. Date de ieşire

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

În fişierul de ieşire $blas.out$ afisati pe T linii cu raspunsul la fiecare test in ordine. Pentru fiecare test, raspunsul e numarul de cifre binare care apar in a N-a secventa, modulo 10067. Afisati rezultatul in baza 10.

h2. Restricţii

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

* 1 ≤ T ≤ 10
* 1 ≤ N ≤ 1000 000 000

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

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

| 2
1
7
| 1
18

|
h3. Explicaţie

...

Prima secventa "1" contine o singura cifra, a 7-a secventa "1 1 1 0 0 1 0 1 1 0 1 1 1 1 0 1 0 1" contine 18 cifre.

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