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$$$.

XOR and Triangle

Examples