Даны два массива неотрицательных целых чисел $$$A=[a_1, a_2, \ldots, a_n]$$$ и $$$B=[b_1, b_2, \ldots, b_m]$$$.
Пусть $$$S(i) = \{j | (a_i \oplus b_j) \leq x\}$$$. Иными словами, $$$S(i)$$$ это множество всех индексов $$$j$$$ массива $$$B$$$, для которых побитовое исключающее или $$$a_i$$$ и $$$b_j$$$ не превосходит $$$x$$$.
Найдите минимальное число $$$k$$$, чтобы можно было покрасить элементы массива $$$A$$$ в $$$k$$$ цветов таким образом, что если $$$S(x)$$$ и $$$S(y)$$$ пересекаются, то $$$x$$$ и $$$y$$$ покрашены в разный цвет.
Иначе говоря, можно найти такие $$$c_1, c_2, \ldots, c_n$$$, что $$$1 \le c_i \le k$$$, и при этом если $$$S(x) \cap S(y) \neq \varnothing$$$, то $$$c_x \neq c_y$$$.
Напомним, что побитовое «исключающее или» ($$$\oplus$$$, xor) двух целых неотрицательных чисел определено следующим образом: запишем оба числа в двоичной системе счисления, $$$i$$$-й двоичный разряд результата равен 1, если ровно у одного из аргументов он равен 1. Например, ($$$14$$$ xor $$$7$$$) = ($$$1110_2 \oplus 0111_2$$$) = $$$1001_2$$$ = $$$9$$$. Эта операция реализована во всех современных языках программирования, в языках C++, Java и Python она записывается как «^{}», в Паскале как «xor».
Входные данные для этой задачи содержат несколько тестовых примеров.
Первая строка ввода содержит одно целое число $$$t$$$ $$$(1 \le t \le 100)$$$ — количество тестовых примеров.
Далее следуют описания тестовых примеров.
В первой строке каждого тестового примера записаны три целых числа $$$n$$$, $$$m$$$ и $$$x$$$ ($$$1 \le n, m \le 500\,000$$$, $$$0 \leq x \lt 2^{30}$$$).
Во второй строке записаны $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ — элементы массива $$$A$$$ ($$$0 \le a_i \lt 2^{30}$$$).
В третьей строке записаны $$$m$$$ целых чисел $$$b_1, b_2, \ldots, b_m$$$ — элементы массива $$$B$$$ ($$$0 \le b_i \lt 2^{30}$$$).
Гарантируется, что как сумма значений $$$n$$$, так и сумма значений $$$m$$$ по всем тестовым примерам не превосходит $$$500\,000$$$.
Для каждого тестового примера выведите одно целое число — минимальное искомое $$$k$$$.
| Подзадача | Баллы | Доп. ограничения | Необх. подзадачи | |
| 1 | 5 | $$$n \le 2$$$ | — | |
| 2 | 5 | $$$n \le 5$$$ | 1 | |
| 3 | 5 | $$$n \le 15$$$ | 1,2 | |
| 4 | 5 | $$$n \le 100$$$ | 1–3 | |
| 5 | 5 | $$$n \le 2\,000$$$ | 1–4 | |
| 6 | 10 | $$$n \le 5\,000$$$ | 1–5 | |
| 7 | 5 | $$$n \le 100\,000$$$, $$$m = 2$$$ | — | |
| 8 | 10 | $$$n \leq 100\,000$$$, $$$m = 3$$$ | — | |
| 9 | 5 | $$$n, m \le 100\,000$$$; $$$a_i, b_i, k | lt; 2$$$ | — |
| 10 | 10 | $$$n, m \le 100\,000$$$; $$$a_i, b_i, k | lt; 4$$$ | 9 |
| 11 | 35 | нет | 1–10 |
32 2 00 01 15 5 30 1 2 3 40 1 2 3 45 5 40 1 2 3 40 1 2 3 4
1 4 5
