Problem C
XOR
Given two non-negative integers $a$ and $n$. You task is to find the minimum non-negative integer $b$ such that $a \oplus b$ is divisible by $n$ (i.e. without remainder).
Here the symbol $\oplus $ denotes ‘XOR’ operation. In order to calculate $x \oplus y$, one has to represent $x$ and $y$ in binary system, and add leading zeros on the left if needed. The result in each position is 1 if and only if the two numbers in that position are different ($0$ and $1$, or 1 and 0). For instance, if $x = 25$ and $y = 44$, then $x \oplus y = 53$.
|
$x$ |
0 |
1 |
1 |
0 |
0 |
1 |
25 |
|
$y$ |
1 |
0 |
1 |
1 |
0 |
0 |
44 |
|
$x\oplus y$ |
1 |
1 |
0 |
1 |
0 |
1 |
53 |
Input
The input consists of several datasets. The first line of the input contains the number of datasets, which is a positive number and is not greater than $10^4$.
Each dataset is described by a line that contains two integers $a$ and $n$ separated by a space (${1 \le a, n \le 10^{18}}$).
Output
For each dataset, write out on one line the found value $b$.
| Sample Input 1 | Sample Output 1 |
|---|---|
3 10 5 3 2 98 100 |
0 1 6 |
