← 返回题目列表

Codeforces · 1775/C

C. 有趣的序列

中文机器翻译题面 查看原题

Petya 和他的朋友机器人 Petya++ 喜欢解决令人兴奋的数学问题。

有一天,Petya++ 提出了数字 $$$n$$$ 和 $$$x$$$,并在黑板上写下了以下等式: $$$$$$n\ \&\ (n+1)\ \&\ \dots\ \&\ m = x,$$$$$$ 其中 $$$\&$$$ 表示按位 AND 运算。然后他建议他的朋友 Petya 找到一个最小的 $$$m$$$ ($$$m \ge n$$$) 以使棋盘上的平等成立。

不幸的是,Petya 无法在头脑中解决这个问题,并决定寻求计算机的帮助。他很快写了一个程序并找到了答案。

你能解决这个难题吗?

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 2000$$$)。测试用例的描述如下。

每个测试用例的唯一行包含两个整数 $$$n$$$, $$$x$$$ ($$$0\le n, x \le 10^{18}$$$)。

输出

对于每个测试用例,输出 $$$m$$$ 的最小可能值,使得相等成立。

如果等式对于任何 $$$m$$$ 不成立,则打印 $$$-1$$$。

我们可以证明,如果所需的 $$$m$$$ 存在,则它不会超过 $$$5 \cdot 10^{18}$$$。

示例

输入 #1

5
10 8
10 10
10 42
20 16
1000000000000000000 0

输出 #1

12
10
-1
24
1152921504606846976

注意

在第一个例子中,$$$10\ \\&\ 11 = 10$$$,但是$$$10\ \&\ 11\ \&\ 12 = 8$$$,所以答案是$$$12$$$。

在第二个示例中,$$$10 = 10$$$,因此答案为 $$$10$$$。

在第三个例子中,我们可以看到所需的$$$m$$$不存在,因此我们必须打印$$$-1$$$。