Олимпиадный тренинг

Задача . C. Микаса


Вам даны два целых числа \(n\) и \(m\). Найдите \(\operatorname{MEX}\) последовательности \(n \oplus 0, n \oplus 1, \ldots, n \oplus m\). Здесь \(\oplus\) обозначает операцию побитового исключающего ИЛИ.

\(\operatorname{MEX}\) последовательности неотрицательных целых чисел — это наименьшее неотрицательное целое число, которое не встречается в этой последовательности. Например, \(\operatorname{MEX}(0, 1, 2, 4) = 3\), а \(\operatorname{MEX}(1, 2021) = 0\).

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

Первая строка содержит одно целое число \(t\) (\(1 \le t \le 30\,000\))  — количество наборов входных данных.

Первая и единственная строка каждого набора входных данных содержит два целых числа \(n\) и \(m\) (\(0 \le n, m \le 10^9\)).

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

Для каждого набора входных данных выведите одно целое число  — ответ на задачу.

Примечание

В первом наборе входных данных последовательность равна \(3 \oplus 0, 3 \oplus 1, 3 \oplus 2, 3 \oplus 3, 3 \oplus 4, 3 \oplus 5\), или \(3, 2, 1, 0, 7, 6\). Наименьшее неотрицательное целое число, которое не присутствует в последовательности, т. е. \(\operatorname{MEX}\) последовательности — \(4\).

Во втором наборе входных данных последовательность равна \(4 \oplus 0, 4 \oplus 1, 4 \oplus 2, 4 \oplus 3, 4 \oplus 4, 4 \oplus 5, 4 \oplus 6\), или \(4, 5, 6, 7, 0, 1, 2\). Наименьшее неотрицательное целое число, которое не присутствует в последовательности, т. е. \(\operatorname{MEX}\) последовательности — \(3\).

В третьем наборе входных данных последовательность равна \(3 \oplus 0, 3 \oplus 1, 3 \oplus 2\), или \(3, 2, 1\). Наименьшее неотрицательное целое число, которое не присутствует в последовательности, т. е. \(\operatorname{MEX}\) последовательности — \(0\).


Примеры
Входные данныеВыходные данные
1 5
3 5
4 6
3 2
69 696
123456 654321
4
3
0
640
530866

time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w645
Комментарий учителя