判断是否存在一个由 $N$ 个非负整数 $a_1, a_2, \dots, a_N$ 组成的序列，满足以下所有条件。如果存在，求出该数组中最大值的最小值。

• $a_1 + a_2 + \dots + a_N = S$
• $a_1 \oplus a_2 \oplus \dots \oplus a_N = X$ （其中 $\oplus$ 表示按位异或运算）

注意，一个输入文件中包含 $T$ 组测试数据。

输入格式

输入通过标准输入给出，格式如下：

$T$ $N_1 \ S_1 \ X_1$ $N_2 \ S_2 \ X_2$ $\vdots$ $N_T \ S_T \ X_T$

其中 $N_i, S_i, X_i$ 分别代表第 $i$ 组测试数据的 $N, S, X$ 值。

数据范围

• $1 \le T \le 500$
• $1 \le N \le 2^{60} - 1$
• $0 \le S \le 2^{60} - 1$
• $0 \le X \le 2^{60} - 1$
• 输入中的所有值均为整数。

输出格式

输出 $T$ 行。对于第 $i$ 组测试数据，如果不存在满足条件的数组，则输出 $-1$；如果存在，则输出该数组中最大值的最小值。

样例

样例输入 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

说明

以下是每组测试数据的一个可行解：

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