Un cocinero se encuentra en un gran dilema. El está trabajando para una fiesta de la oficina corporativa y está ocupado preparando diferentes platos. El anfitrión de la fiesta le ha insistido en que se prepare sus deliciosos pastelitos de postre.

En el día de la fiesta, el anfitrión se mostró satisfecho con todo lo preparado y servido para la fiesta excepto por los pastelitos. El anfitrión se dio cuenta de que estaban dispuestas de forma ordenada en la forma de un rectángulo. Entonces le pide al cocinero que reordene los pastelitos de modo que sea lo más cuadrado posible.

El cocinero no está de humor para perder tiempo ordenando sus pastelitos en un cuadrado perfecto. Sin embargo para engañar al anfitrión, te pide organizar los N pastelitos como un rectángulo de forma que la diferencia se reduce al mínimo entre la longitud y la anchura.

Input

La primera línea del INPUT comienza con un número M que indica el número de casos del problema propuesto. (1 ≤ M ≤ 50)

Cada caso está compuesto de la(s) siguiente(s) linea(s):

Cada caso contiene un solo entero N, que denota el número de pastelitos.

Restricciones.

1 ≤ N ≤ 10 ^ 9

Output

Salida para cada caso. Un entero indicando la diferencia mínima posible entre la longitud y la anchura en una disposición rectangular de los pastelitos.

Entrada de ejemplo

Explicación

Caso 1 : 20 pastelitos pueden estar dispuestos en 6 posibles maneras: 1 x 20, 2 x 10, 4 x 5, 5 x 4, 10 x 2 y 20 x 1 Las diferencias correspondientes entre la longitud y la anchura son 19, 8 , 1, 1, 8 y 19, respectivamente. Por lo tanto, 1 es la respuesta.

Caso 4 : 4 pastelitos se pueden organizar como un cuadrado de 2 x 2. Diferencia entre la longitud y el ancho es de 0. No se puede hacer nada mejor que 0.