Problem Statement

You are given two positive integers $N$ and $K$. A positive integer $X$ is called compatible with $N$ if it satisfies the following condition:

• The bitwise XOR of $X$ and $N$ is equal to the remainder when $X$ is divided by $N$.

Determine whether there exist at least $K$ such integers $X$ that are compatible with $N$. If they do exist, find the $K$-th smallest such integer.

You are given $T$ test cases; solve each of them.

About XOR The bitwise XOR of nonnegative integers $A$ and $B$, denoted $A\ \mathrm{XOR}\ B$, is defined as follows: In the binary representation of $A\ \mathrm{XOR}\ B$, the digit in the $2^k$ place (for $k \geq 0$) is $1$ if and only if exactly one of $A$ and $B$ has a $1$ in the $2^k$ place in its binary representation. Otherwise, it is $0$. For example, $3\ \mathrm{XOR}\ 5 = 6$ (in binary: $011\ \mathrm{XOR}\ 101 = 110$).

Constraints

• $1 \le T \le 2\times 10^5$
• $1 \le N,K \le 10^9$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T

Here, $\text{case}_i$ denotes the $i$-th test case. Each test case is given in the following format:

N K

Output

For each test case, if there exist at least $K$ positive integers that are compatible with $N$, print the $K$-th smallest such integer. Otherwise, print -1.