Mówimy, że ciąg liczb całkowitych $C = c_1, c_2, \dots, c_k$ o długości $k$ jest dobry, jeśli średnia arytmetyczna jego najmniejszego i największego elementu jest równa jego medianie. Mediana ciągu o długości $k$ jest zdefiniowana jako $\lceil \frac{k}{2} \rceil$-ty najmniejszy element w ciągu, gdzie $\lceil x \rceil$ to najmniejsza liczba całkowita większa lub równa $x$. Na przykład, medianą ciągu $1, 7, 4, 3$ jest $3$, podczas gdy medianą ciągu $5, 8, 2, 1, 6$ jest $5$.

Mówiąc bardziej formalnie, niech $D = d_1, d_2, \dots, d_k$ będzie ciągiem otrzymanym przez posortowanie ciągu $C$ w kolejności niemalejącej. Ciąg $C$ jest dobry, jeśli:

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

Mając dany ciąg liczb całkowitych $A = a_1, a_2, \dots, a_n$, oblicz długość jego najdłuższego dobrego podciągu. Przypomnijmy, że ciąg $B$ jest podciągiem ciągu $A$, jeśli $B$ można otrzymać poprzez usunięcie pewnych (lub żadnych) elementów z $A$, bez zmiany kolejności pozostałych elementów.

Wejście

Dostępnych jest wiele zestawów danych testowych. Pierwsza linia wejścia zawiera liczbę całkowitą $T$ ($1 \le T \le 300$) określającą liczbę zestawów danych. Dla każdego zestawu danych:

Pierwsza linia zawiera liczbę całkowitą $n$ ($1 \le n \le 3 \times 10^3$), określającą długość ciągu. Druga linia zawiera $n$ liczb całkowitych $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$), określających ciąg.

Gwarantuje się, że suma $n$ dla wszystkich zestawów danych nie przekracza $3 \times 10^3$.

Wyjście

Dla każdego zestawu danych wypisz w jednej linii jedną liczbę całkowitą, określającą długość najdłuższego dobrego podciągu.

Przykład

Wejście 1

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

Wyjście 1

5
4
1
2

Uwagi

Dla pierwszego przykładowego zestawu danych, najdłuższy dobry podciąg to $3, 5, 8, 2, 5$. Jego najmniejszym elementem jest $2$, największym $8$, a medianą $5$.

Dla drugiego przykładowego zestawu danych, najdłuższy dobry podciąg to $7, 9, 4, 10$. Jego najmniejszym elementem jest $4$, największym $10$, a medianą $7$.