«Exclusive or» Strikes Back

Two non-negative integers $a$ and $n$ are given. Find the smallest non-negative integer $b$ such that $a \oplus b$ is divisible by $n$.

Here $\oplus$ denotes the bitwise «exclusive or» operation and corresponds to the «xor» operation in Pascal or to «\char 94» in other languages. To compute the bitwise «exclusive or» of two numbers $x$ and $y$, write each of them in binary, padding with leading zeros on the left if needed. The result in each position is 1 if exactly one of the numbers has a 1 in the corresponding position. For example, for $x=12$ and $y=26$ the result is 22.

The first line of input contains the number $t$, the number of test cases ($1 \le t \le 10^4$). The next $t$ lines contain the descriptions of the test cases. Each description consists of two numbers $a$ and $n$ separated by a space ($1 \le a, n \le 10^{18}$).

For each test case, output the required $b$ as a single number.