長さ $k$ の整数列 $C = c_1, c_2, \dots, c_k$ について、その最小値と最大値の平均が中央値と等しいとき、この列を「良い」列と呼ぶことにします。長さ $k$ の列の中央値は、列を昇順に並べ替えたものを $D = d_1, d_2, \dots, d_k$ としたとき、$d_{\lceil k/2 \rceil}$ と定義されます。ここで $\lceil x \rceil$ は $x$ 以上の最小の整数を表します。例えば、数列 $1, 7, 4, 3$ の中央値は $3$ であり、数列 $5, 8, 2, 1, 6$ の中央値は $5$ です。

より厳密には、数列 $C$ を昇順に並べ替えたものを $D = d_1, d_2, \dots, d_k$ とすると、$C$ が良い列であるとは、以下の式が成り立つことを指します。

$$\frac{d_1 + d_k}{2} = d_{\lceil k/2 \rceil}$$

整数列 $A = a_1, a_2, \dots, a_n$ が与えられます。この数列の「良い」部分列のうち、最長のものの長さを求めてください。なお、数列 $B$ が $A$ の部分列であるとは、$A$ からいくつかの要素（0個でもよい）を削除し、残りの要素の順序を変えずに得られる数列であることを指します。

入力

入力は複数のテストケースから構成されます。最初の行にはテストケースの数 $T$ ($1 \le T \le 300$) が含まれます。各テストケースは以下の形式で与えられます。

1行目には整数 $n$ ($1 \le n \le 3 \times 10^3$) が与えられ、数列の長さを表します。 2行目には $n$ 個の整数 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$) が与えられ、数列を表します。

すべてのテストケースにおける $n$ の総和は $3 \times 10^3$ を超えないことが保証されています。

出力

各テストケースについて、最長の良い部分列の長さを1行で出力してください。

入出力例

入出力例 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

注記

1つ目のサンプルテストケースにおいて、最長の良い部分列は $3, 5, 8, 2, 5$ です。この列の最小値は $2$、最大値は $8$、中央値は $5$ です。

2つ目のサンプルテストケースにおいて、最長の良い部分列は $7, 9, 4, 10$ です。この列の最小値は $4$、最大値は $10$、中央値は $7$ です。