B. Split
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a sequence $$$a$$$ containing $$$2n$$$ integers. Let $$$f(b)$$$ denote the number of distinct elements with an odd number of occurrences in sequence $$$b$$$. You need to split the given array into two disjoint subsequences $$$p$$$ and $$$q$$$, each of size $$$n$$$, such that $$$f(p) + f(q)$$$ is maximized. Output the maximum value.

A sequence $$$a$$$ is a subsequence of a sequence $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by the deletion of several (possibly, zero or all) element from arbitrary positions.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains an integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$).

The second line contains $$$2n$$$ integers $$$a_1,a_2,\ldots,a_{2n}$$$ ($$$1 \le a_i \le 2n$$$) — the elements of sequence $$$a$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, print one line.

You have to print the maximum value of $$$f(p) + f(q)$$$ that can be achieved.

Example
Input
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
Output
4
2
4
0
8
4
2
Note

For the first test case:

  • We can divide the array such that $$$p = [1, 3]$$$ and $$$q = [2, 4]$$$.
  • This way, $$$f(p) = 2$$$ and $$$f(q) = 2$$$ since both have two distinct elements with odd frequency.

For the second test case:

  • We can divide the array such that $$$p = [5, 5, 5]$$$ and $$$q = [5, 5, 5]$$$.
  • This way, $$$f(p) = 1$$$ and $$$f(q) = 1$$$.

For the fifth test case:

  • We can divide the array such that $$$p = [1, 2, 3, 4, 5, 6]$$$ and $$$q = [4, 1, 4, 1, 5, 4]$$$.
  • This way, $$$f(p) = 6$$$ and $$$f(q) = 2$$$.