teddy online judge

73. Extinción Maya

Limite de tiempo : 1 seg.   Total runs : 151  Aceptados : 63

La civilizacion Maya fue una de las mas desarrolladas e inteligentes de la era precolombina en la antigua mesoamerica, sus conocimientos y descubrimientos han aportado al desarrollo humano hoy en dia. Se dice que desaparecieron sin dejar rastro alguno, pero la verdad ha sido ocultada durante años. Realmente fueron exterminados por alienigenas que temian ser superados por los conocimientos de nuestros ancestros, solo algunos o mejor dicho muy pocos lograron escapar de aquella masacre.

Recordemos que esta cultura es recordada como mistica y misteriosa. Entonces para lograr esconderse desarrollaron una habilidad magica y matematica, la cual consistia en escalar una de sus piramides, colocarse en uno de los escalones y pronunciar el numero de rocas que habian sido utilizadas para construir la piramide desde el tope (escalon 1) hasta dicho escalon, y asi traspasar la piramide hasta un lugar seguro. Ahora tu mision es ayudar a los pocos mayas que quedan vivos dentro de la piramide, tendras que invertir el proceso que ellos realizaron para esconderse. La entrada sera un numero n que contiene el numero de piedras usadas para construir la piramide desde el tope de la piramide hasta cierto escalon. Tu debes encontrar a que escalon pertenece. Para ello tienes que saber que los escalones se acomodan de la siguiente manera:

           
            1    *tope    1 piedras en el escalon 1
           121            4 piedras en el escalon 2
          12321           9 piedras en el escalon 3                         .
         1234321                              
        123454321                             
       12345654321            
      1234567654321
     123456787654321
    12345678987654321
   1234567890987654321
  123456789010987654321
 12345678901210987654321
1234567890123210987654321
            .
            .
            .

Entonces se usaron 14 (1+4+9) piedras hasta el escalon 3.

Entrada

La entrada consiste en un entero p menor a 1000 que es el numero de casos de prueba, le siguen p lineas con el entero n donde 1 < n < 2²⁹ que es el numero de piedras usadas desde el tope hasta cierto escalon.

Salida

La salida debe mostrar el escalon donde se encuentra el maya.

Ejemplo

Entrada (data.in)

4
14
30
55
2015

Salida (data.out)

3
4
5
22

Autor: Gerardo S. Reyes Perez