Похищение века
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Талантливый картёжник Фукс, работающий охранником в Королевском музее искусств, решает встать на дорогу криминала. Мафиозный Шеф поручает Фуксу похитить скульптуру Венеры Милосской, спрятав её в футляре от контрабаса. Фуксу известно о сигнализации, которую необходимо отключить, чтобы похищение прошло тихо.

На панели управления сигнализацией расположены массив из $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ и массив из $$$n$$$ целых чисел $$$b_1, b_2, \ldots, b_n$$$. Паролем является количество пар индексов $$$(i, j)$$$ ($$$1 \le i, j \le n$$$), таких что $$$a_i \oplus b_j = k$$$ и $$$a_j \oplus b_i = m$$$. Операция $$$\oplus$$$ обозначает побитовое исключающее ИЛИ. Обратите внимание, что пары $$$(i, j)$$$ и $$$(j, i)$$$ ($$$1 \le i \lt j \le n$$$) считаются различными.

Фукс по характеру неуверенный и боится действовать самостоятельно. Помогите ему определить пароль от панели управления сигнализацией.

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

В первой строке дано целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных.

В первой строке каждого набора даны три целых числа $$$n$$$, $$$k$$$, $$$m$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$0 \le k, m \le 2^{31} - 1$$$) — длина массивов и параметры пароля.

Во второй строке каждого набора даны $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 2^{31} - 1$$$) — первый массив.

В третьей строке каждого набора даны $$$n$$$ целых чисел $$$b_1, b_2, \ldots, b_n$$$ ($$$0 \le b_i \le 2^{31} - 1$$$) — второй массив.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2\cdot 10^5$$$.

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

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

Пример

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

    45 3 47 2 8 1 51 2 3 5 44 0 02 2 3 32 2 3 35 6 07 3 9 1 33 1 2 2 13 3 41 2 35 6 7

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

    1820

Примечание

В первом наборе входных данных подходит пара индексов $$$(1, 5)$$$ ($$$a_1 \oplus b_5 = 7 \oplus 4 = 3$$$, $$$a_5 \oplus b_1 = 5 \oplus 1 = 4$$$). Можно показать, что другие пары индексов не подходят, значит паролем является число $$$1$$$.