시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 0 0 0 0.000%

문제

Даны два неотрицательных целых числа $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$.

예제 입력 1

3
10 5
3 2
98 100

예제 출력 1

0
1
6