«Виключне або» завдає удару у відповідь
Дано два невід'ємних цілих числа 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.