A José le han asignado la tarea de encontrar el dulce mágico, en una bolsa de dulces. Todos los dulces estan numerados de 1 a n, y el dulce mágico se halla con el siguiente procedimiento:
- Mientras exista un dulce.
- Descarta todos los dulces que están en posiciones que corresponden a un cuadrado perfecto, por ejemplo los dulces que están en las posiciones 1,4,9,16,25,etc.
- Enumerar todos los dulces manteniendo el orden original.
- Repetir el proceso, cuando quede un solo dulce, encontraste el dulce mágico.
Veamos un ejemplo, supongamos que tenemos 9 dulces y cada uno tiene una etiqueta: ABCDEFGHI
- Paso 1: Descartar los dulces de las posiciones que corresponden a un cuadrado perfecto, 1,4,9(A,D,I).
- Paso 2: Repetimos el proceso con los dulces restantes BCEFGH.
- Paso 3: Descartar los dulces de las posiciones 1,4(B,F).
- Paso 4: Quedan CEGH por lo que hay que descartar 1,4(C,H).
- Paso 5: Quedan EG por lo que descartamos el dulce 1 que es E.
- El dulce mágico es G.
Dato que el dulce mágico estaba en la séptima posición debe dar como respuesta 7.
La primera linea contiene el numero de casos de prueba. Las linea siguientes contienen un caso de prueba consiste en el numero (2 ≤ n ≤ 1,000) de dulces.
Por cada caso de prueba imprima en una linea la posición donde se encuentra el dulce mágico.
4 5 9 20 1
5 7 17 1
#2012