A piece of glazed glass of size $n$ falls from the sky and shatters into lustrous crystal fragments, where the size of each fragment is a positive integer.

Ling gently picks up these shimmering fragments. In her eyes, a fragment of size $x$ is a "beautiful fragment" if and only if $x$ is an odd number greater than 1.

Given the condition that all fragments must be beautiful fragments, Ling wants to know the maximum possible number of fragments. If it is impossible for all fragments to be beautiful, output -1.

Input

The input contains multiple test cases. The first line contains a single positive integer $T$ ($1 \le T \le 10^4$), representing the number of test cases.

For each test case: A single line contains a positive integer $n$ ($1 \le n \le 10^9$), representing the size of the glazed glass, which is the sum of the sizes of all fragments.

Output

For each test case: A single line containing an integer, representing the maximum number of fragments such that all fragments are beautiful. If it is impossible for all fragments to be beautiful, output -1.

Examples

Input 1

6
1
3
5
7
8
9

Output 1

-1
1
1
1
2
3

Note

For $n = 3$, $n = 5$, and $n = 7$, the maximum number of fragments is clearly 1. For $n = 8$, the maximum number of fragments is 2, where the sizes of the fragments are 3 and 5. For $n = 9$, the maximum number of fragments is 3, where the sizes of the fragments are 3, 3, and 3.