D. Феникс и носки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Чтобы удовлетворить свою любовь к собиранию носков в пары, Феникс принес свои $$$n$$$ носков ($$$n$$$ — четное) в магазин по продаже носков. Каждый его носок определенного цвета $$$c_i$$$ и либо левый, либо правый.

Феникс может заплатить один доллар магазину, чтобы:

  • либо перекрасить какой-то носок в любой цвет $$$c'$$$ $$$(1 \le c' \le n)$$$,
  • либо превратить левый носок в правый,
  • либо превратить правый носок в левый.

Магазин может производить любое из изменений любое количество раз. Заметим, что цвет левого носка не меняется, когда он превращается в правый, и наоборот.

Два носка образуют пару, если это левый и правый носок одинакового цвета. Какую минимальное количество денег нужно заплатить Фениксу, чтобы собрать $$$n/2$$$ пар? Каждый носок должен попасть ровно в одну пару.

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

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

В первой строке каждого набора заданы три целых числа $$$n$$$, $$$l$$$ и $$$r$$$ ($$$2 \le n \le 2 \cdot 10^5$$$; $$$n$$$ — четное; $$$0 \le l, r \le n$$$; $$$l+r=n$$$) — общее количество носков и количество левых и правых носков соответственно.

В следующей строке заданы $$$n$$$ целых чисел $$$c_i$$$ ($$$1 \le c_i \le n$$$) — цвета носков. Первые $$$l$$$ носков — левые, остальные $$$r$$$ носков — правые.

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

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

Для каждого набора входных данных, выведите одно число — минимальное количество денег, которое нужно заплатить Фениксу, чтобы собрать $$$n/2$$$ пар носков. Каждый носок должен попасть ровно в одну пару.

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

В первом наборе, Феникс может заплатить $$$2$$$ доллара для того, чтобы:

  • перекрасить носок $$$1$$$ в цвет $$$2$$$,
  • перекрасить носок $$$3$$$ в цвет $$$2$$$.
В результате он получит $$$3$$$ пары. Например, пары $$$(1, 4)$$$, $$$(2, 5)$$$ и $$$(3, 6)$$$.

Во втором наборе, Феникс может заплатить $$$3$$$ доллара, чтобы:

  • превратить носок $$$6$$$ из правого в левый,
  • перекрасить носок $$$3$$$ в цвет $$$1$$$,
  • перекрасить носок $$$4$$$ в цвет $$$1$$$.
В результате он получит $$$3$$$ пары. Например, пары $$$(1, 3)$$$, $$$(2, 4)$$$ и $$$(5, 6)$$$.