有一个包含 $N$ 个整数的序列。我们希望重新排列这些整数，使其尽可能“优美”。如果一个序列中，有更多的元素不小于其相邻元素，那么这个序列就更优美。序列的“优美度”定义为满足该条件的元素个数。

编写一个程序，将给定的序列重新排列，使其优美度达到最大。

例如，如果 $N = 6$ 且序列为 $1, 1, 2, 3, 3, 4$，原序列的优美度为 $3$。然而，如果我们将其重新排列为 $2, 1, 3, 3, 1, 4$，则重排后序列的优美度为 $4$，这是可能达到的最大值。

输入格式

第一行包含一个整数 $T$，表示测试用例的数量 ($1 \le T \le 2222$)。接下来是各测试用例。 每个测试用例的第一行包含一个整数 $N$，表示元素的数量 ($1 \le N \le 300\,000$)。 下一行包含序列的元素。每个元素都是 $1$ 到 $10^9$ 之间的整数（包含边界）。 所有测试用例的 $N$ 之和不超过 $5\,000\,000$。

输出格式

对于每个测试用例，输出一行，包含一个整数：重排后可能达到的最高优美度。

样例

样例输入 1

2
6
1 1 2 3 3 4
5
1 2 2 3 3

样例输出 1

4
4