Даны два неотрицательных целых числа \(a\) и \(n\). Требуется найти такое минимальное неотрицательное число \(b\), что \(a \oplus b\) нацело делится на \(n\).
Здесь \(\oplus\) обозначает операцию побитового «исключающего или» и соответствует операции «xor» в Паскале или «^» в других языках. Для вычисления побитового «исключающего или» двух чисел \(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\).
3 10 5 3 2 98 100
0 1 6