Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana

Muchos de ustedes han oído hablar de la criba de Eratóstenes. Es un algoritmo que puede encontrar todos los números primos entre $1$ y $N$. El algoritmo funciona de la siguiente manera:

Vamos a imprimir todos los números de $1$ y $N$. En el primer paso, eliminar todos los números divisibles por 2, excepto 2.
En el segundo paso, elimine todos los números divisibles por $3$ excepto $3$. En el $k-ésimo$ paso, quite todos los números divisibles por $k + 1$ excepto $k + 1$ (algunos de los números pueden haber sido eliminados antes). No es difícil mostrar que después de N pasos, sólo los números primos y 1 todavía no se eliminarán. Consideremos una modificación de este algoritmo. En el $k-ésimo$ paso, elimine cada $(k + 1) -ésimo$ número de la lista de números que aún no han sido eliminados. Así, en el primer paso, todos los números pares serán eliminados. Los números eliminados en el segundo paso son 5, 11, 17, .... Después de infinitos pasos, la secuencia restante comenzará como 1, 3, 7, 13, 19, 27, 39, 49, ....

Su tarea es verificar si el número dado $N$ está en la secuencia, y si es así, encuentre su posición en la secuencia, empezando por 1.

Input

La primera línea de entrada contiene un entero $T$: el número de casos de prueba $(1 \leq T \leq 50)$. Las siguientes $T$  líneas contienen números enteros $N_1, N_2, ..., N_T$ para los que hay que resolver el problema $(1 \leq N_i \leq 10^{12})$.

Output

Para cada caso de prueba, imprima la posición numérica de $N_i$ en la secuencia o -1 si no está en la secuencia.

Sample test(s)