Fa uns 4600 anys, a l’antic Egipte, el petit Imhotep, quan s’avorria a l’escola, es dedicava a apilar cubs de fusta. Amb el temps, aquella afició esdevingué professió i acabà construint la primera piràmide de l’imperi, a Saqqara.

Imhotep sempre deia: "Tot a la vida són patrons... fins i tot els cubs!" Com que moure els blocs de pedra podia trigar dies, Imhotep disposava de molt temps lliure mentre supervisava les obres, i solia plantejar reptes als seus aprenents.

Un dia els va deixar escrit en un papir:

"Si apilo cubs formant una piràmide quadrada perfecta —amb una base de N×N, sobre la qual hi poso una capa de (N−1)×(N−1), i així successivament fins arribar a 1×1 al cim—, quants cubs necessito en total?"

Però el repte no acabava aquí. Imhotep també volia saber:

"Donada una quantitat de cubs, quina és la piràmide quadrada més gran que puc construir?"

Exemples

• Amb 14 cubs puc fer una piràmide de mida 3 (1 + 4 + 9 = 14). Perfecte!
• Amb 15 cubs també puc fer una piràmide de mida 3 (en sobra 1, però no n’hi ha prou per fer una de mida 4, que en necessita 30).
• Amb 5 cubs només puc fer una piràmide de mida 2 (1 + 4 = 5).

Entrada

La primera línia conté un valor enter que indica el nombre de casos de prova.

Per a cada cas de prova, hi haurà un únic enter C (0 ≤ C ≤ 1.000.000), que representa la quantitat de cubs disponibles.

Sortida

Per a cada cas de prova cal indicar la mida N de la piràmide quadrada més gran que es pot construir amb els cubs disponibles. No cal considerar els cubs que puguin sobrar, ja que no permeten completar una nova planta.

Si amb la quantitat donada no es pot construir ni tan sols una piràmide de mida 1 (que requereix 1 cub), s’ha de mostrar 0.

Exemple d'Entrada

5
14
0
5
1
30

Exemple de Sortida

3
0
2
1
4