Xor Sum

Determine whether there exists a sequence of $N$ nonnegative integers $a_1, a_2, \cdots, a_N$ that satisfies both of the following conditions. If it exists, find the minimum possible value of the maximum element of the sequence.

• $a_1+a_2+\cdots+a_N=S$
• $a_1 \oplus a_2 \oplus \cdots \oplus a_N=X$ ($\oplus$ is the bitwise xor operation)

The input file contains $T$ tests.

Input is given from standard input in the following format:

$T$

$N_1$ $S_1$ $X_1$

$N_2$ $S_2$ $X_2$

$\vdots$

$N_T$ $S_T$ $X_T$

Here, $N_i$, $S_i$, and $X_i$ are the values of $N$, $S$, and $X$ for the $i$-th test.

Print $T$ lines. On the $i$-th line, print $-1$ if no sequence satisfies the conditions in the $i$-th test. Otherwise, print the minimum possible value of the maximum element.

• $1 \leq T \leq 500$
• $1 \leq N \leq 2^{60}-1$
• $0 \leq S \leq 2^{60}-1$
• $0 \leq X \leq 2^{60}-1$
• All values in the input are integers.

The following is a solution for each test:

• (3,3,3)
• (2,2,2,2)
• (2,3,3,3,4,4)
• (15)
• Impossible
• Impossible