D. Максимальное И
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам даны два массива $$$a$$$ и $$$b$$$, состоящие из $$$n$$$ целых чисел каждый.

Определим функцию $$$f(a, b)$$$ следующим образом:

  • определим массив $$$c$$$ размера $$$n$$$, где $$$c_i = a_i \oplus b_i$$$ ($$$\oplus$$$ обозначает операцию побитового исключающего ИЛИ);
  • значением функции является $$$c_1 \mathbin{\&} c_2 \mathbin{\&} \cdots \mathbin{\&} c_n$$$ (т.е. побитовое И всех элементов массива $$$c$$$).

Найдите максимальное значение функции $$$f(a, b)$$$, если вы можете переупорядочить элементы массива $$$b$$$ произвольным образом (также можно оставить первоначальный порядок).

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

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

Первая строка каждого набора содержит одно целое число $$$n$$$ ($$$1 \le n \le 10^5$$$) — размеры массивов $$$a$$$ и $$$b$$$.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i < 2^{30}$$$).

Третья строка содержит $$$n$$$ целых чисел $$$b_1, b_2, \dots, b_n$$$ ($$$0 \le b_i < 2^{30}$$$).

Сумма $$$n$$$ по всем наборам входных данных не превосходит $$$10^5$$$.

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

Для каждого набора входных данных выведите одно целое число — максимальное значение функции $$$f(a, b)$$$, если вы можете переупорядочить элементы массива $$$b$$$ произвольным образом.

Пример
Входные данные
3
5
1 0 0 3 3
2 3 2 1 0
3
1 1 1
0 0 3
8
0 1 2 3 4 5 6 7
7 6 5 4 3 2 1 0
Выходные данные
2
0
7