"Exclusive Or" Strikes Back
Given two non-negative integers a and n, your task is to determine the smallest non-negative integer b such that a xor b is divisible by n.
The operation xor refers to the bitwise "exclusive or" operation, which is represented by "xor" in Pascal or "^" in many other programming languages. To perform the bitwise "exclusive or" on two numbers x and y, you must first express them in binary form, adding leading zeros if necessary to align their lengths. The result for each bit position is 1 if and only if one of the numbers has a 1 in that position, but not both. For instance, for x = 12 and y = 26, the result is 22:
Input
The first line contains the number of test cases t (1 ≤ t ≤ 10^4
). Each of the next t lines provides a test case with two numbers a and n, separated by a space (1 ≤ a, n ≤ 10^18
).
Output
For each test case, output a single number, which is the required b.