Un trozo de vidrio esmaltado de tamaño $n$ cae desde el aire y se rompe en fragmentos brillantes; el tamaño de cada fragmento es un número entero positivo.

Aya observa estos fragmentos brillantes y, a sus ojos, un fragmento de tamaño $x$ es un "fragmento hermoso" si y solo si $x$ es un número impar mayor que 1.

Bajo la condición de que todos los fragmentos sean hermosos, Aya quiere conocer el valor máximo de la cantidad de fragmentos. Si no existe una situación en la que todos los fragmentos sean hermosos, responde -1.

Entrada

El problema contiene múltiples casos de prueba. La primera línea contiene un número entero positivo $T$ ($1 \le T \le 10^4$), que representa el número de casos de prueba.

Para cada caso de prueba: Una línea con un número entero positivo $n$ ($1 \le n \le 10^9$), que representa el tamaño del vidrio esmaltado, es decir, la suma de los tamaños de todos los fragmentos.

Salida

Para cada caso de prueba: Una línea con un número entero que representa el valor máximo de la cantidad de fragmentos bajo la condición de que todos sean hermosos. Si no existe tal situación, imprime -1.

Ejemplos

Entrada 1

6
1
3
5
7
8
9

Salida 1

-1
1
1
1
2
3

Nota

Para $n = 3$, $n = 5$ y $n = 7$, la cantidad máxima de fragmentos es obviamente 1. Para $n = 8$, la cantidad máxima de fragmentos es 2, donde los tamaños de los fragmentos son 3 y 5. Para $n = 9$, la cantidad máxima de fragmentos es 3, donde los tamaños de los fragmentos son 3, 3 y 3.