Un barajeo perfecto (out-shuffle) es un tipo de mezcla donde un mazo con un número par de cartas se divide exactamente por la mitad, y las dos mitades se intercalan perfectamente. Por ejemplo, si tenemos un mazo de 8 cartas representadas por 'ABCDEFGH', la primera mitad es 'ABCD' y la segunda mitad es 'EFGH'. Al intercalarse empezando por la primera carta de la primera mitad, el nuevo orden resulta en 'AEBFCGDH'. Tenga en cuenta que la carta superior (en este caso 'A') permanece arriba.

Si realizamos varias veces este proceso a un mazo de 8 cartas:

1. 'ABCDEFGH' $\rightarrow$ 'AEBFCGDH'
2. 'AEBFCGDH' $\rightarrow$ 'ACEGBDFH'
3. 'ACEGBDFH' $\rightarrow$ 'ABCDEFGH'

Después de 3 barajeos, el mazo vuelve a su estado original.

Dado el número de cartas $N$ de un mazo (donde $N$ es siempre un número par), determina la cantidad mínima de barajeos perfectos necesarios para que el mazo vuelva a su orden original.

La entrada consiste en varios casos de prueba. La primera línea contiene un número entero $T$ que indica cuántos casos de prueba existen. A continuación, siguen $T$ líneas, cada una con un entero par $N$ que representa el número de cartas del mazo.

Para cada caso de prueba, imprima en una nueva línea un entero que represente el número mínimo de barajeos requeridos para volver al orden original.