eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

«Исключающее или» наносит ответный удар

«Исключающее или» наносит ответный удар

Лимит времени 1 секунда
Лимит использования памяти 122 MiB

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

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

prb7794.gif

Входные данные

В первой строке содержится количество тестов t (1t10^4). В следующих t строках содержатся описания тестовых примеров. Каждое описание состоит из двух чисел a и n, разделенных пробелом (1a, n10^18).

Выходные данные

Для каждого теста вывести единственное число - искомое b.

Пример

Входные данные #1
3
10 5
3 2
98 100
Выходные данные #1
0
1
6
Источник 2016 XVII Всероссийская командная олимпиада школьников по программированию, 11 декабря, Задача K