{"raw_statement":[{"iden":"problem statement","content":"You are given two positive integers $N$ and $K$. A positive integer $X$ is called **compatible with $N$** if it satisfies the following condition:\n\n*   The bitwise XOR of $X$ and $N$ is equal to the remainder when $X$ is divided by $N$.\n\nDetermine 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.\nYou are given $T$ test cases; solve each of them.\nAbout XORThe bitwise XOR of nonnegative integers $A$ and $B$, denoted $A\\ \\mathrm{XOR}\\ B$, is defined as follows:\n\n*   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$.\n\nFor example, $3\\ \\mathrm{XOR}\\ 5 = 6$ (in binary: $011\\ \\mathrm{XOR}\\ 101 = 110$)."},{"iden":"constraints","content":"*   $1 \\le T \\le 2\\times 10^5$\n*   $1 \\le N,K \\le 10^9$\n*   All input values are integers."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$T$\n$\\text{case}_1$\n$\\text{case}_2$\n$\\vdots$\n$\\text{case}_T$\n\nHere, $\\text{case}_i$ denotes the $i$\\-th test case.  \nEach test case is given in the following format:\n\n$N$ $K$"},{"iden":"sample input 1","content":"4\n2 1\n2 2\n1 7\n20250126 191"},{"iden":"sample output 1","content":"2\n3\n-1\n20381694\n\nConsider the case $N=2$.\n\n*   When $X=1$, $X\\ \\mathrm{XOR}\\ N = 3$ and the remainder of $X$ when divided by $N$ is $1$. Therefore, $1$ is not compatible with $N$.\n*   When $X=2$, $X\\ \\mathrm{XOR}\\ N = 0$ and the remainder of $X$ when divided by $N$ is $0$. Therefore, $2$ is compatible with $N$.\n*   When $X=3$, $X\\ \\mathrm{XOR}\\ N = 1$ and the remainder of $X$ when divided by $N$ is $1$. Therefore, $3$ is compatible with $N$.\n\nHence, among the numbers that are compatible with $2$, the smallest is $2$ and the second smallest is $3$. Therefore, the answer to $\\text{case}_1$ is $2$ and the answer to $\\text{case}_2$ is $3$."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}