On a recent birthday, your best friend Maurice gave you a pair of numbers $$$n$$$ and $$$x$$$, and asked you to construct an array of positive numbers $$$a$$$ of length $$$n$$$ such that $$$a_1 \oplus a_2 \oplus \cdots \oplus a_n = x$$$ $$$^{\text{∗}}$$$.

This task seemed too simple to you, and therefore you decided to give Maurice a return gift by constructing an array among all such arrays that has the smallest sum of its elements. You immediately thought of a suitable array; however, since writing it down turned out to be too time-consuming, Maurice will have to settle for just the sum of its elements.

$$$^{\text{∗}}$$$$$$\oplus$$$ denotes the bitwise XOR operation.

Input

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

Each test case consists of a single line containing a pair of numbers $$$n$$$ and $$$x$$$ ($$$1 \le n \le 10^9, \; 0 \le x \le 10^9$$$) — the numbers given to you by Maurice.

Output

For each test case, output your gift to Maurice — the sum of the elements of the array that satisfies all the described properties. If a suitable array does not exist, output $$$-1$$$.

Note

In the first test case, one of the suitable arrays is $$$[2, 3]$$$. It can be shown that it is impossible to achieve a smaller sum of array elements.

In the second case, one of the suitable arrays is $$$[1, 3, 4]$$$. It can also be shown that this is the optimal amount.

SUMdamental Decomposition

Examples