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