This time, the pink soldiers have given you an integer $x$ ($x \ge 2$).

Please determine if there exists a positive integer $y$ that satisfies the following conditions.

• $y$ is strictly less than $x$.
• There exists a non-degenerate triangle$^{\text{∗}}$ with side lengths $x$, $y$, $x \oplus y$. Here, $\oplus$ denotes the bitwise XOR operation.

Additionally, if there exists such an integer $y$, output any.

$^{\text{∗}}$A triangle with side lengths $a$, $b$, $c$ is non-degenerate when $a+b \gt c$, $a+c \gt b$, $b+c \gt a$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 2000$). The description of the test cases follows.

The only line of each test case contains a single integer $x$ ($2 \le x \le 10^9$).

Output

For each test case, print one integer on a separate line. The integer you must output is as follows:

• If there exists an integer $y$ satisfying the conditions, output the value of $y$ ($1 \le y \lt x$);
• Otherwise, output $-1$.

If there exist multiple integers that satisfy the conditions, you may output any.

Note

In the first test case, there exists a non-degenerate triangle with side lengths $3$, $5$, and $3 \oplus 5 = 6$. Therefore, $y=3$ is a valid answer.

In the second test case, $1$ is the only possible candidate for $y$, but it cannot make a non-degenerate triangle. Therefore, the answer is $-1$.

Samples

7
5
2
6
3
69
4
420

3
-1
5
-1
66
-1
320