D. World is Mine
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Alice and Bob are playing a game. Initially, there are $$$n$$$ cakes, with the $$$i$$$-th cake having a tastiness value of $$$a_i$$$.

Alice and Bob take turns eating them, with Alice starting first:

  • In her turn, Alice chooses and eats any remaining cake whose tastiness is strictly greater than the maximum tastiness of any of the cakes she's eaten before that. Note that on the first turn, she can choose any cake.
  • In his turn, Bob chooses any remaining cake and eats it.

The game ends when the current player can't eat a suitable cake. Let $$$x$$$ be the number of cakes that Alice ate. Then, Alice wants to maximize $$$x$$$, while Bob wants to minimize $$$x$$$.

Find out how many cakes Alice will eat if both players play optimally.

Input

Each test contains multiple test cases. The first line of input contains a single integer $$$t$$$ ($$$1 \le t \le 500$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 5000$$$) — the number of cakes.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — the tastiness values of the cakes.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5000$$$.

Output

For each test case, output a single integer — the number of cakes Alice will eat if both players play optimally.

Example
Input
9
4
1 4 2 3
3
1 1 1
5
1 4 2 3 4
4
3 4 1 4
1
1
8
4 3 2 5 6 8 3 4
7
6 1 1 3 5 3 1
11
6 11 6 8 7 5 3 11 2 3 5
17
2 6 5 3 9 1 6 2 5 6 3 2 3 9 6 1 6
Output
2
1
3
2
1
3
2
4
4
Note

In the first test case, one possible sequence of turns is:

  1. Alice eats a cake with a tastiness value of $$$1$$$. The remaining cakes are $$$[4, 2, 3]$$$.
  2. Bob eats a cake with a tastiness value of $$$2$$$. The remaining cakes are $$$[4, 3]$$$.
  3. Alice eats a cake with a tastiness of $$$3$$$. The remaining cakes are $$$[4]$$$.
  4. Bob eats a cake with a tastiness value of $$$4$$$. The remaining cakes are $$$[]$$$.
  5. Since there are no more cakes left, the game ends.

In the second test case, one possible sequence of turns is:

  1. Alice eats a cake with a tastiness value of $$$1$$$. The remaining cakes are $$$[1, 1]$$$.
  2. Bob eats a cake with a tastiness value of $$$1$$$. The remaining cakes are $$$[1]$$$.
  3. Since Alice has already eaten a cake with a tastiness value of $$$1$$$, she cannot make a turn, so the game ends.