D. Xor Sum
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

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

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

Note that there are $$$T$$$ tests in one input file.

Input

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,X_i$$$ represent values of $$$N,S,X$$$ for the $$$i$$$-th test, respectively.

Constraints:

  • $$$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 input are integers.
Output

Print $$$T$$$ lines. In the $$$i$$$-th line, print $$$-1$$$ if there doesn't exist an array with the mentioned property in the $$$i$$$-th test, and print the minimum possible value of the maximum of the array if it exists.

Example
Input
6
3 9 3
4 8 0
6 19 1
1 15 15
2 6 5
5 4 3
Output
3
2
4
15
-1
-1
Note

The following is a solution for each test:

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