We say an integer sequence $$$C = c_1, c_2, \cdots, 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, \cdots, 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, \cdots, 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.
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, \cdots, 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$$$.
For each test case, output one line containing one integer, indicating the length of the longest good subsequence.
473 5 9 8 2 11 577 9 2 4 17 10 1511002100 100
5 4 1 2
For the first sample test case, the longest good subsequence is $$$3, 5, 8, 2, 5$$$. It's 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$$$. It's smallest element is $$$4$$$, largest element is $$$10$$$, and median is $$$7$$$.
