e-olymp
Yarışlar

XOR Contest

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

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

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

prb7794.gif

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

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

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

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

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 122.17 MiB
Giriş verilənləri #1
3
10 5
3 2
98 100
Çıxış verilənləri #1
0
1
6
Mənbə 2016 XVII Всероссийская командная олимпиада школьников по программированию, 11 декабря, Задача K