CF1775C.Interesting Sequence

普及/提高-

通过率:0%

AC君温馨提醒

该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。

题目描述

Petya and his friend, robot Petya++, like to solve exciting math problems.

One day Petya++ came up with the numbers nn and xx and wrote the following equality on the board: $$$$n\ &\ (n+1)\ &\ \dots\ &\ m = x, $$ where \\& denotes the bitwise AND operation. Then he suggested his friend Petya find such a minimal mm ( mgenm \\ge n$$) that the equality on the board holds.

Unfortunately, Petya couldn't solve this problem in his head and decided to ask for computer help. He quickly wrote a program and found the answer.

Can you solve this difficult problem?

输入格式

Each test contains multiple test cases. The first line contains the number of test cases tt ( 1t20001 \le t \le 2000 ). The description of the test cases follows.

The only line of each test case contains two integers nn , xx ( 0n,x10180\le n, x \le 10^{18} ).

输出格式

For every test case, output the smallest possible value of mm such that equality holds.

If the equality does not hold for any mm , print 1-1 instead.

We can show that if the required mm exists, it does not exceed 510185 \cdot 10^{18} .

输入输出样例

  • 输入#1

    5
    10 8
    10 10
    10 42
    20 16
    1000000000000000000 0

    输出#1

    12
    10
    -1
    24
    1152921504606846976

说明/提示

In the first example, 10 & 11=1010\ \&\ 11 = 10 , but 10 & 11 & 12=810\ \&\ 11\ \&\ 12 = 8 , so the answer is 1212 .

In the second example, 10=1010 = 10 , so the answer is 1010 .

In the third example, we can see that the required mm does not exist, so we have to print 1-1 .

首页