Alice and Bob play a game. There are $$$n$$$ marbles, the $$$i$$$-th of them has color $$$c_i$$$. The players take turns; Alice goes first, then Bob, then Alice again, then Bob again, and so on.

During their turn, a player must take one of the remaining marbles and remove it from the game. If there are no marbles left (all $$$n$$$ marbles have been taken), the game ends.

Alice's score at the end of the game is calculated as follows:

she receives $$$1$$$ point for every color $$$x$$$ such that she has taken at least one marble of that color;
additionally, she receives $$$1$$$ point for every color $$$x$$$ such that she has taken all marbles of that color (of course, only colors present in the game are considered).

For example, suppose there are $$$5$$$ marbles, their colors are $$$[1, 3, 1, 3, 4]$$$, and the game goes as follows: Alice takes the $$$1$$$-st marble, then Bob takes the $$$3$$$-rd marble, then Alice takes the $$$5$$$-th marble, then Bob takes the $$$2$$$-nd marble, and finally, Alice takes the $$$4$$$-th marble. Then, Alice receives $$$4$$$ points: $$$3$$$ points for having at least one marble for colors $$$1$$$, $$$3$$$ and $$$4$$$, and $$$1$$$ point for having all marbles of color $$$4$$$. Note that this strategy is not necessarily optimal for both players.

Alice wants to maximize her score at the end of the game. Bob wants to minimize it. Both players play optimally (i. e. Alice chooses a strategy which allows her to get as many points as possible, and Bob chooses a strategy which minimizes the amount of points Alice can get).

Calculate Alice's score at the end of the game.

Input

The first line contains one integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases.

Each test case consists of two lines:

the first line contains one integer $$$n$$$ ($$$1 \le n \le 1000$$$) — the number of marbles;
the second line contains $$$n$$$ integers $$$c_1, c_2, \dots, c_n$$$ ($$$1 \le c_i \le n$$$) — the colors of the marbles.

Additional constraint on the input: the sum of $$$n$$$ over all test cases does not exceed $$$1000$$$.

Output

For each test case, print one integer — Alice's score at the end of the game, assuming that both players play optimally.

Note

In the second test case of the example, the colors of all marbles are distinct, so, no matter how the players act, Alice receives $$$4$$$ points for having all marbles of two colors, and no marbles of the third color.

In the third test case of the example, the colors of all marbles are the same, so, no matter how the players act, Alice receives $$$1$$$ point for having at least one (but not all) marble of color $$$4$$$.

Game with Colored Marbles

Examples