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.

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$$$.

Split

Examples