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

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

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

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

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

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