Un número triangular es un entero positivo de la forma ~1+2+\dots+k~. Los primeros números triangulares son ~1, 3, 6, 10~ y ~15~. Todo entero positivo se puede representar como una suma de números triangulares. Por ejemplo, ~42 = 21 + 21~ y ~1337 = 1326 + 10 + 1~.

Dado un entero positivo ~n~, determine el menor número de números triangulares cuya suma sea ~n~.

Entrada

La primera línea tiene un entero ~t~: el número de pruebas. Después, cada línea tiene un entero positivo ~n~.

Salida

Para cada prueba, imprima el menor número de números triangulares.

Restricciones

• ~1 \leq t \leq 100~
• ~1 \leq n \leq 10^{12}~

Ejemplo de Entrada

5
1
2
3
42
1337

Ejemplo de Salida

1
2
1
2
3