Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
C. Interesting Sequence

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

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

One day Petya++ came up with the numbers $$$n$$$ and $$$x$$$ 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 $$$m$$$ ($$$m \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?

Input

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

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

Output

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

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

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

Example

Input

510 810 1010 4220 161000000000000000000 0

Output

12 10 -1 24 1152921504606846976

Note

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

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

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

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/08/2023 20:51:01 (i2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|