Scări

Cerință

Gigi este un pasionat constructor și astăzi analizează un detaliu foarte important în orice construcții: scările. O scară poate fi reprezentată ca o mulțime de dale într-un tablou. O scară de nivel $n$ are $n$ coloane: prima coloană are înălțimea $1$, a doua are înălțimea $2$, $\dots$, ultima are înălțimea $n$.
O scară de nivel $n$ este frumoasă dacă poate fi acoperită de $n$ pătrate de orice dimensiuni, disjuncte. (În imagine scara este de nivel $7$. Sunt utilizate $4$ pătrate verzi de dimensiune $1 \times 1$, fiecare folosind o dală, $2$ pătrate galbene de dimensiune $2 \times 2$, fiecare folosind $4$ dale, și un pătrat roșu de dimensiune $4 \times 4$ ce folosește $16$ dale). Gigi primește întrebări definite prin câte un număr $K$ și trebuie să răspundă cu un număr ce reprezintă numărul de scări frumoase care au nivele diferite pe care le poate construi folosind maxim $K$ dale.

Cunoscând $Q$ numărul de întrebări și numărul de dale pentru fiecare întrebare se cere să determinați răspunsul lor.

Date de intrare

Pe prima linie a fișierului de intrare scari.in se găsește un număr $Q$ reprezentând numărul de întrebări. Următoarele $Q$ linii au un singur număr întreg, $k$ care reprezintă numărul de dale pe care le poate folosi.

Date de ieșire

În fișierul de ieșire scari.out se vor găsi $Q$ linii, pe fiecare aflându-se un singur număr ce reprezintă numărul maxim de scări frumoase care pot fi construite folosind maxim $k$ dale.

Restricții și precizări

• $Q \leq 1 \ 000$;
• $K \leq 1 \ 000 \ 000 \ 000 \ 000 \ 000 \ 000$;
• Pentru $20\%$ din teste $Q \leq 20$ și $K \leq 100$.

Exemplu

scari.in

4
1
8
6
100

scari.out

1
2
1
3

Explicație

Pentru $1$: cu o singură dală, putem construi o singură scară de nivel $1$.
Pentru $8$: cu $8$ dale putem construi doar $2$ scări frumoase: una de nivel $1$ (costă $1$) și încă una de nivel $3$ (care costă $6$). În total cheltuim $7$ (ultima dală rămasă nu o mai putem folosi pentru a crea o scară interesantă de nivel diferit de $1$ și de $3$). Foarte important: scara de nivel $2$ nu este frumoasă (nu poate fi colorată în $2$ pătrate).