题目描述

编舞师 Aina 正在给一排舞者重新安排站位。每名舞者手里拿着一个整数牌，所有牌上的数构成一个长度为 $N$ 的序列。

她认为，一个位置如果不低于自己的相邻位置，就会显得更醒目。具体地，对于重排后的序列，若某个元素不小于它所有存在的相邻元素，则称这个元素是漂亮的。序列的漂亮度定义为漂亮元素的数量。

端点只有一个相邻元素，也按同样规则判断。

Aina 可以任意重排给定的 $N$ 个整数。请你求出重排后能够达到的最大漂亮度。

例如，当 $N=6$，原序列为 $1,1,2,3,3,4$ 时，原序列的漂亮度为 $3$。若重排为 $2,1,3,3,1,4$，漂亮度为 $4$，并且这是最大可能值。

输入格式

第一行包含一个整数 $T$，表示测试数据组数。

对于每组测试数据：

第一行包含一个整数 $N$，表示序列长度。

第二行包含 $N$ 个整数，表示序列中的元素。

输出格式

对于每组测试数据，输出一行一个整数，表示重排后可能达到的最大漂亮度。

数据范围

• $1\le T\le 2222$；
• $1\le N\le 300000$；
• 每个元素都是 $[1,10^9]$ 内的整数；
• 所有测试数据中 $N$ 的总和不超过 $5000000$。

样例 1

输入

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

输出

4
4