F. Beautiful Sequence
time limit per test
4 seconds
memory limit per test
1024 mebibytes
input
standard input
output
standard output

There is a sequence consisting of $$$N$$$ integers. We want to rearrange the integers to make the most beautiful sequence possible. A sequence is more beautiful when there are more members which are not less than their neighbors. The beauty of a sequence is the number of such members.

Write a program that will rearrange a given sequence to make it the most beautiful possible.

For example, if $$$N = 6$$$ and the sequence is $$$1, 1, 2, 3, 3, 4$$$, the beauty of the given sequence is $$$3$$$. However, if we rearrange the sequence to become $$$2, 1, 3, 3, 1, 4$$$, then the beauty of the rearranged sequence is $$$4$$$, which is the maximum possible.

Input

The first line contains an integer $$$T$$$, the number of test cases ($$$1 \le T \le 2222$$$). The test cases follow.

The first line of each test case contains an integer $$$N$$$, the number of elements ($$$1 \le N \le 300\,000$$$).

The next line contains the elements of the sequence. Each element is an integer between $$$1$$$ and $$$10^9$$$, inclusive.

The sum of $$$N$$$ over all test cases does not exceed $$$5\,000\,000$$$.

Output

For each test case, print one line containing an integer: the highest beauty possible after rearrangement.

Example
Input
2
6
1 1 2 3 3 4
5
1 2 2 3 3
Output
4
4