Мы называем целочисленную последовательность $C = c_1, c_2, \dots, c_k$ длины $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

Пример 2

5
4
1
2

Примечание

Для первого примера самая длинная хорошая подпоследовательность — $3, 5, 8, 2, 5$. Её наименьший элемент равен $2$, наибольший — $8$, а медиана — $5$.

Для второго примера самая длинная хорошая подпоследовательность — $7, 9, 4, 10$. Её наименьший элемент равен $4$, наибольший — $10$, а медиана — $7$.