我们称一个长度为 $k$ 的整数序列 $C = c_1, c_2, \dots, c_k$ 是好的，如果其最小元素和最大元素的平均值等于其中位数。长度为 $k$ 的序列的中位数定义为该序列中第 $\lceil \frac{k}{2} \rceil$ 小的元素，其中 $\lceil x \rceil$ 表示大于或等于 $x$ 的最小整数。例如，序列 $1, 7, 4, 3$ 的中位数是 $3$，而序列 $5, 8, 2, 1, 6$ 的中位数是 $5$。

更正式地说，令 $D = d_1, d_2, \dots, d_k$ 为序列 $C$ 从小到大排序后得到的序列。$C$ 是好的，当且仅当： $$\frac{d_1 + d_k}{2} = d_{\lceil \frac{k}{2} \rceil}$$

给定一个整数序列 $A = a_1, a_2, \dots, a_n$，计算其最长的好子序列的长度。回想一下，如果序列 $B$ 可以通过从 $A$ 中删除零个或多个元素（不改变剩余元素的顺序）得到，则称 $B$ 是 $A$ 的子序列。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$ ($1 \le T \le 300$)，表示测试数据的组数。对于每组测试数据：

第一行包含一个整数 $n$ ($1 \le n \le 3 \times 10^3$)，表示序列的长度。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$)，表示该序列。

保证所有测试数据的 $n$ 之和不超过 $3 \times 10^3$。

输出格式

对于每组测试数据，输出一行，包含一个整数，表示最长的好子序列的长度。

样例

输入 1

4
7
3 5 9 8 2 11 5
7
7 9 2 4 17 10 15
1
100
2
100 100

输出 1

5
4
1
2

说明

对于第一个样例测试数据，最长的好子序列是 $3, 5, 8, 2, 5$。其最小元素为 $2$，最大元素为 $8$，中位数为 $5$。

对于第二个样例测试数据，最长的好子序列是 $7, 9, 4, 10$。其最小元素为 $4$，最大元素为 $10$，中位数为 $7$。