为了满足他对搭配袜子的热爱,菲尼克斯把他的 $$$n$$$ 袜子($$$n$$$ 是偶数)带到了袜子店。他的每只袜子都有一个颜色 $$$c_i$$$ 并且是左袜子或右袜子。
Phoenix 可以向袜子店支付 1 美元来执行以下任一操作:
- 将袜子重新着色为任意颜色 $$$c'$$$ $$$(1 \le c' \le n)$$$
- 将左袜子变成右袜子
- 将右袜子变成左袜子
袜子存储可以执行这些更改中的每一个任意次数。请注意,当左袜子变成右袜子时,其颜色不会改变,反之亦然。
一双配套的袜子是左右一只袜子颜色相同。 Phoenix 制造 $$$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$$$。
输出
对于每个测试用例,打印一个整数 - Phoenix 生成 $$$n/2$$$ 匹配对的最低成本。每只袜子必须完全匹配。
示例
输入 #1
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
输出 #1
2 3 5 3
注意
在第一个测试用例中,Phoenix 可以向以下对象支付 $$$2$$$ 美元:
- 将袜子 $$$1$$$ 重新着色为 $$$2$$$
- 将袜子 $$$3$$$ 重新着色为 $$$2$$$
在第二个测试用例中,Phoenix 可以向以下对象支付 $$$3$$$ 美元:
- 将袜子$$$6$$$从右袜子变成左袜子
- 将袜子 $$$3$$$ 重新着色为 $$$1$$$
- 将袜子 $$$4$$$ 重新着色为 $$$1$$$