B. XOR последовательности
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам даны два различных целых неотрицательных числа $$$x$$$ и $$$y$$$. Рассмотрим две бесконечные последовательности $$$a_1, a_2, a_3, \ldots$$$ и $$$b_1, b_2, b_3, \ldots$$$, где

  • $$$a_n = n \oplus x$$$;
  • $$$b_n = n \oplus y$$$.

Здесь $$$x \oplus y$$$ обозначает операцию побитового исключающего ИЛИ чисел $$$x$$$ и $$$y$$$.

Например, при $$$x = 6$$$, первые $$$8$$$ элементов последовательности $$$a$$$ будут выглядеть следующим образом: $$$[7, 4, 5, 2, 3, 0, 1, 14, \ldots]$$$. Обратите внимание, что индексы элементов начинаются с $$$1$$$.

Ваша задача — найти длину наибольшего общего подотрезка$$$^\dagger$$$ последовательностей $$$a$$$ и $$$b$$$. Другими словами, найдите такое максимальное целое число $$$m$$$, что $$$a_i = b_j, a_{i + 1} = b_{j + 1}, \ldots, a_{i + m - 1} = b_{j + m - 1}$$$ для некоторых $$$i, j \ge 1$$$.

$$$^\dagger$$$Подотрезком последовательности $$$p$$$ называется последовательность $$$p_l,p_{l+1},\ldots,p_r$$$, где $$$1 \le l \le r$$$.

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

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит единственное целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Единственная строка каждого набора входных данных содержит два целых числа $$$x$$$ и $$$y$$$ ($$$0 \le x, y \le 10^9, x \neq y$$$) — параметры последовательностей.

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

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

Пример
Входные данные
4
0 1
12 4
57 37
316560849 14570961
Выходные данные
1
8
4
33554432
Примечание

В первом наборе входных данных первые $$$7$$$ элементов последовательностей $$$a$$$ и $$$b$$$ следующие:

$$$a = [1, 2, 3, 4, 5, 6, 7,\ldots]$$$

$$$b = [0, 3, 2, 5, 4, 7, 6,\ldots]$$$

Можно показать, что не существуют такого целого положительного числа $$$k$$$, что отрезок $$$[k, k + 1]$$$ встречается в $$$b$$$ как подотрезок. Поэтому ответ равен $$$1$$$.

В третьем наборе входных данных первые $$$20$$$ элементов последовательностей $$$a$$$ и $$$b$$$ следующие:

$$$a = [56, 59, 58, 61, 60, 63, 62, 49, 48, 51, 50, 53, 52, 55, 54, \textbf{41, 40, 43, 42}, 45, \ldots]$$$

$$$b = [36, 39, 38, 33, 32, 35, 34, 45, 44, 47, 46, \textbf{41, 40, 43, 42}, 53, 52, 55, 54, 49, \ldots]$$$

Можно показать, что одним из наибольших общих подотрезков является подотрезок $$$[41, 40, 43, 42]$$$, длина которого равна $$$4$$$.