codeforces#P2074C. XOR and Triangle
XOR and Triangle
Description
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$.
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$).
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.
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.
7
5
2
6
3
69
4
420
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$.