C. XOR and Triangle
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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 > c$$$, $$$a+c > b$$$, $$$b+c > 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 < x$$$);
  • Otherwise, output $$$-1$$$.

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

Example
Input
7
5
2
6
3
69
4
420
Output
3
-1
5
-1
66
-1
320
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$$$.