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

Bugland are o populatie mixta, avand ca populatie atat gandaci cu $2$ antene cat si gandaci cu $3$ antene.
In mod evident, gandacii cu $2$ antene numara in baza $2$ (de altfel ei zic ca sunt $10$ tipuri de gandaci in Bugland), si cei cu $3$ antene numara in baza $3$.

Bugland are o populaţie mixtă, având ca populaţie atât gândaci cu $2$ antene cât şi gândaci cu $3$ antene.
În mod evident, gândacii cu $2$ antene numără în baza $2$ (de altfel ei zic că sunt $10$ tipuri de gândaci în Bugland), şi cei cu $3$ antene numără în baza $3$.

Un numar este considerat nepotrivit daca cele doua specii de gandaci il privesc ca avand suma cifrelor diferita. Altfel spus, un numar este nepotrivit daca suma cifrelor din scrierea lui in baza $2$ si in baza $3$ difera.

Un număr este considerat nepotrivit dacă cele două specii de gândaci îl privesc ca având suma cifrelor diferită. Altfel spus, un număr este nepotrivit dacă suma cifrelor din scrierea lui în baza $2$ şi în baza $3$ diferă.
Pentru a promova egalitatea gândacilor, numerele nepotrivite sunt stric interzise.

In mod evident, pentru a promova egalitatea gandacilor, numerele nepotrivite sunt interzise.
Avand in vedere ca gandacii nu stiu sa numere decat pana la N, cate numere permise exista?

Avand în vedere că gândacii nu ştiu să numere decât de la 1 până la N, câte numere permise există?

h2. Date de intrare

Fişierul de intrare $23.in$ contine $T$, numarul de scenarii.
Urmatoarele $T$ linii contin cate un numar $N$, cel mai mare numar pe care gandacii il stiu.
De observat ca gandacii stiu numai numere naturale.

Din $23.in$ se va citi de pe prima linie numărul $T$ de scenarii.
Următoarele $T$ linii conţin câte un numar $N$, cel mai mare număr pe care gândacii îl ştiu. De observat că gândacii ştiu numai numere naturale.

h2. Date de ieşire

În fişierul de ieşire $23.out$ va contine $T$ linii, pe a $i$-a linie fiind raspunsul la al $i$-lea scenariu.

În $23.out$ se vor afişa $T$ numere pe o singură linie, separate prin spaţiu, al $i$-lea număr fiind răspunsul la al $i$-lea scenariu.

h2. Restricţii

* $1 ≤ T ≤ 100.000$
* $1 ≤ N~i~ ≤ 10^7^$

* <tex>1 \leq T \leq 1000</tex>
* <tex>1 \leq N_i \leq 10^7</tex>
* Pentru teste in valoare de $20$ de puncte, <tex>1 \leq \displaystyle{\sum_{i=0}^{T} N_i} \leq 10^6</tex>
* Pentru alte teste in valoare de $30 de puncte$, <tex>1 \leq N_i \leq 10^6</tex>

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

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

| 10
1 2 3 4 5 6 7 8 9 10
| 1 1 1 1 1 2 3 3 3 4

|
h3. Explicaţie

...

Numerele de la $1$ la $10$ sunt scrise în baza $2$, respectiv $3$ astfel:
 
|_. baza 10 |_. baza2 |_. baza 3 |_. suma în baza 2 |_. suma în baza 3 |
| 1 | 1 | 1 | 1 | 1 |
| 2 | 10 | 2 | 1 | 2 |
| 3 | 11 | 10 | 2 | 1 |
| 4 | 100 | 11 | 1 | 2 |
| 5 | 101 | 12 | 2 | 3 |
| 6 | 110 | 20 | 2 | 2 |
| 7 | 111 | 21 | 3 | 3 |
| 8 | 1000 | 22 | 1 | 4 |
| 9 | 1001 | 100 | 2 | 1 |
| 10 | 1010 | 101 | 2 | 2 |
 
Astfel, numerele permise sunt $1, 6, 7, 10$.
 
Numerele permise sunt $1, 6, 7, 10$.

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