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:
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.
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$$$.
For each test case, output a single integer — the number of cakes Alice will eat if both players play optimally.
941 4 2 331 1 151 4 2 3 443 4 1 41184 3 2 5 6 8 3 476 1 1 3 5 3 1116 11 6 8 7 5 3 11 2 3 5172 6 5 3 9 1 6 2 5 6 3 2 3 9 6 1 6
2 1 3 2 1 3 2 4 4
In the first test case, one possible sequence of turns is:
In the second test case, one possible sequence of turns is:
Name |
---|