题目描述

给定一个长度为 $2n$ 的序列 $a$。对于任意序列 $b$，令 $f(b)$ 表示在序列 $b$ 中 出现次数为奇数 的不同元素的个数。现要求把序列 $a$ 拆成两个互不相交的子序列 $p$ 和 $q$，且每个子序列的长度均为 $n$，使得 $f(p)+f(q)$ 最大。输出该最大值。

这里子序列的定义为：从序列中删除若干（也可以不删除）元素后保留原相对顺序得到的新序列。

输入格式

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例数。接下来依次为 $t$ 个测试用例。

每个测试用例包含两行：

• 第一行：一个整数 $n$（$1\le n\le 2\cdot10^5$）。
• 第二行：$2n$ 个整数 $a_1,a_2,\dots,a_{2n}$（$1\le a_i\le 2n$），表示序列 $a$ 的各个元素。

额外约束：所有测试用例中 $\sum n \le 2\cdot10^5$。

输出格式

对每个测试用例，输出一行，包含一个整数——可以达到的最大值 $f(p)+f(q)$。

样例输入

7
2
1 2 3 4
3
5 5 5 5 5 5
4
3 3 7 6 3 7 8 7
2
2 2 2 2
6
1 2 3 4 5 4 1 4 1 5 4 6
4
1 2 1 2 1 2 1 2
5
9 9 9 7 7 7 9 7 7 7

样例输出

4
2
4
0
8
4
2