問題文

非負整数 $N$ が与えられます。非負整数 $k$ であって、 $\lfloor \sqrt{k} \rfloor \oplus k = N$ となるものがあるかどうか判定し、あれば $1$ つ見つけてください。

ただし、 $\oplus$ は bitwise xor を表すとします。また、実数 $x$ に対して $\lfloor x \rfloor$ は、 $x$ を超えない最大の整数を表すものとします。たとえば $\lfloor 3.14 \rfloor = 3, \lfloor 4 \rfloor = 4$ となります。

$T$ 個のテストケースが与えられるので、それぞれについて解いてください。

制約

• 入力はすべて整数
• $1 \le T \le 100$

各テストケースに対して、

• $0 \le N \lt 2^{60}$

入力

$T$
$\text{case}_1$
$\text{case}_2$
$\vdots$
$\text{case}_T$

$N$

出力

$T$ 行出力せよ。 $i$ $(1\le i\le T)$ 行目には、 $i$ 番目のテストケースの $N$ について、$\lfloor \sqrt{k} \rfloor \oplus k = N$ となる非負整数 $k$ がある場合は $k$ の値を $1$ つ出力し、そのような非負整数 $k$ がない場合は -1 を出力せよ。

サンプル

8
1
2
10
0
11
12
998244353
1152921504606846975

-1
3
9
0
-1
15
998275946
1152921503533105152