We say an integer sequence $C = c_1, c_2, \dots, c_k$ of length $k$ is good if the average value of its smallest element and its largest element is equal to its median. The median of a sequence of length $k$ is defined to be the $\lceil \frac{k}{2} \rceil$-th smallest element in the sequence, where $\lceil x \rceil$ is the smallest integer larger than or equal to $x$. For example, the median of sequence $1, 7, 4, 3$ is $3$, while the median of sequence $5, 8, 2, 1, 6$ is $5$.

More formally, let $D = d_1, d_2, \dots, d_k$ be the sequence obtained by sorting sequence $C$ from small to large. $C$ is good if

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

Given an integer sequence $A = a_1, a_2, \dots, a_n$, calculate the length of its longest good subsequence. Recall that a sequence $B$ is a subsequence of $A$ if $B$ can be obtained by deleting some or no elements from $A$, without changing the order of the remaining elements.

Input

There are multiple test cases. The first line of the input contains an integer $T$ ($1 \le T \le 300$) indicating the number of test cases. For each test case:

The first line contains an integer $n$ ($1 \le n \le 3 \times 10^3$), indicating the length of the sequence. The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$), indicating the sequence.

It’s guaranteed that the sum of $n$ of all test cases does not exceed $3 \times 10^3$.

Output

For each test case, output one line containing one integer, indicating the length of the longest good subsequence.

Examples

Input 1

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

Output 1

5
4
1
2

Note

For the first sample test case, the longest good subsequence is $3, 5, 8, 2, 5$. Its smallest element is $2$, largest element is $8$, and median is $5$.

For the second sample test case, the longest good subsequence is $7, 9, 4, 10$. Its smallest element is $4$, largest element is $10$, and median is $7$.