一塊大小為 $n$ 的彩釉玻璃自空中墜落，碎裂成瑩潤的碎晶，每片碎晶的大小皆為正整數。

綾輕捻這些閃爍的碎晶，於她眼中，一片大小為 $x$ 的碎晶是美麗的碎晶，當且僅當 $x$ 是大於 $1$ 的奇數。

在所有碎晶都是美麗的碎晶的前提下，綾想知道碎晶數量的最大值。若不存在所有碎晶都是美麗的碎晶的情況，回答 -1 即可。

輸入格式

本題有多組數據。第一行一個正整數 $T$ ($1 \le T \le 10^4$)，表示數據組數。

對於每組數據： 一行一個正整數 $n$ ($1 \le n \le 10^9$)，表示彩釉玻璃的大小，即所有碎晶的大小之和。

輸出格式

對於每組數據： 一行一個整數，表示在所有碎晶都是美麗的碎晶的情況下，碎晶數量的最大值。若不存在所有碎晶都是美麗的碎晶的情況，輸出 -1。

範例

輸入 1

6
1
3
5
7
8
9

輸出 1

-1
1
1
1
2
3

說明 1

當 $n = 3, n = 5, n = 7$ 時，碎晶的最大數量顯然為 $1$。 當 $n = 8$ 時，碎晶的最大數量為 $2$，此時碎晶的大小分別為 $3, 5$。 當 $n = 9$ 時，碎晶的最大數量為 $3$，此時碎晶的大小分別為 $3, 3, 3$。