Problema número 414

Conseguir un cuadrado perfecto

Tiempo máximo: 2,000-3,000 sMemoria máxima: 4096 KiB
Cuadrados imperfectos

Un número es un cuadrado perfecto si su raíz cuadrada es un número exacto (sin decimales). Por ejemplo, el 4 es un cuadrado perfecto (2²), al igual que lo son el 36 (6²) y el 3.500.641 (1871²).

Todos los números que no son cuadrados perfectos pueden multiplicarse por otros para conseguir serlo. Por ejemplo, el número 8 no es un cuadrado perfecto, pero al multiplicarlo por 2 se obtiene el 16, que sí lo es.

Entrada

La entrada comienza con un número que indica cuántos casos de prueba tendrán que procesarse.

Cada caso de prueba consiste en un número mayor que 0 y menor que 231.

Salida

Para cada caso de prueba, el programa escribirá por la salida estándar, en una línea independiente, el número más pequeño que al ser multiplicado por el número del caso de prueba da como resultado un cuadrado perfecto.

Entrada de ejemplo

3
4
8
12

Salida de ejemplo

1
2
3