大きさ $n$ の彩釉ガラスが空中から落下し、輝く結晶に砕けました。各結晶の大きさはすべて正の整数です。

綾はこれらの輝く結晶を手に取りました。彼女の目には、大きさ $x$ の結晶は、$x$ が 1 より大きい奇数である場合に限り「美しい結晶」として映ります。

すべての結晶が美しい結晶であるという条件下で、結晶の個数の最大値を求めてください。すべての結晶が美しい結晶となるような状況が存在しない場合は、-1 と答えてください。

入力

入力は複数のテストケースから構成されます。最初の行にテストケースの数 $T$ ($1 \le T \le 10^4$) が与えられます。

各テストケースは以下の形式で与えられます。

1 行に正の整数 $n$ ($1 \le n \le 10^9$) が与えられます。これは彩釉ガラスの大きさ、すなわちすべての結晶の大きさの合計を表します。

出力

各テストケースについて、すべての結晶が美しい結晶であるという条件下での結晶の個数の最大値を 1 行に出力してください。すべての結晶が美しい結晶となるような状況が存在しない場合は、-1 を出力してください。

入出力例

入力 1

6
1
3
5
7
8
9

出力 1

-1
1
1
1
2
3

注記

$n = 3, n = 5, n = 7$ のとき、結晶の最大個数は明らかに 1 です。 $n = 8$ のとき、結晶の最大個数は 2 であり、このとき結晶の大きさはそれぞれ 3, 5 です。 $n = 9$ のとき、結晶の最大個数は 3 であり、このとき結晶の大きさはそれぞれ 3, 3, 3 です。