我們稱一個長度為 $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$。