«Исключающее или» наносит ответный удар
Даны два неотрицательных целых числа a и n. Требуется найти такое минимальное неотрицательное число b, что a xor b нацело делится на n.
Здесь xor обозначает операцию побитового «исключающего или» и соответствует операции «xor» в Паскале или «^» в других языках. Для вычисления побитового «исключающего или» двух чисел x и y необходимо записать каждое из них в двоичной системе счисления, дополнив, при необходимости, ведущими нулями слева. Результат в каждой позиции равен 1 в том случае, если в точности в одном из чисел в соответствующей позиции находится 1. К примеру, для чисел x = 12 и y = 26 результат равен 22:
Входные данные
В первой строке содержится количество тестов t (1 ≤ t ≤ 10^4). В следующих t строках содержатся описания тестовых примеров. Каждое описание состоит из двух чисел a и n, разделенных пробелом (1 ≤ a, n ≤ 10^18).
Выходные данные
Для каждого теста вывести единственное число - искомое b.