시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 (추가 시간 없음) 1024 MB111100.000%

문제

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

출력

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.

제한

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

예제 입력 1

6
3 9 3
4 8 0
6 19 1
1 15 15
2 6 5
5 4 3

예제 출력 1

3
2
4
15
-1
-1

노트

The following is a solution for each test:

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