题目描述

给定两个非负整数 a 和 n。

请找到最小的非负整数 b，使得：

(a xor b) 可以被 n 整除

这里 xor 表示按位异或运算，在 C++ 中对应运算符 ^。

按位异或的定义如下：将两个数写成二进制表示，必要时在左侧补前导零。对于每一个二进制位，如果两个数在该位上的值不同，则结果该位为 1；否则为 0。

例如：

x = 12 = 01100
 y = 26 = 11010
x xor y = 10110 = 22

输入格式

第一行输入一个整数 t，表示测试用例数量。

接下来 t 行，每行输入两个整数 a, n。

输出格式

对于每个测试用例，输出一行一个整数，表示满足条件的最小非负整数 b。

数据范围

• 1 ≤ t ≤ 100000
• 1 ≤ a, n ≤ 10^18
• 约 30% 的测试中，min(a, n) ≤ 100
• 约 80% 的测试中，t ≤ 10000

样例

输入

3
10 5
3 2
98 100

输出

0
1
6