19869번 - <<Исключающее или>> наносит ответный удар 스페셜 저지다국어

문제

Даны два неотрицательных целых числа $a$ и $n$. Требуется найти такое минимальное неотрицательное число $b,ドル что $a \oplus b$ нацело делится на $n$.

Здесь $\oplus$ обозначает операцию побитового <<исключающего или>> и соответствует операции <<xor>> в Паскале или <<\char 94>> в других языках. Для вычисления побитового <<исключающего или>> двух чисел $x$ и $y$ необходимо записать каждое из них в двоичной системе счисления, дополнив, при необходимости, ведущими нулями слева. Результат в каждой позиции равен 1 в том случае, если в точности в одном из чисел в соответствующей позиции находится 1. К примеру, для чисел $x=12$ и $y=26$ результат равен 22:

입력

В первой строке входных данных содержится число $t$ --- количество тестовых примеров (1ドル \le t \le 10^4$). В следующих $t$ строках содержатся описания тестовых примеров. Каждое описание состоит из двух чисел $a$ и $n,ドル разделенных пробелом (1ドル \le a, n \le 10^{18}$).

출력

Для каждого из тестовых примеров требуется вывести единственное число --- искомое $b$.

제한

힌트