You are given an array $$$a$$$ with an odd length $$$n$$$ consisting of positive integers. You are required to partition the sequence into several subarrays$$$^{\text{∗}}$$$ with odd lengths and the same median$$$^{\text{†}}$$$. Your task is to find the maximum number of subarrays.

More formally, you are required to find a strictly-increasing sequence $$$k$$$ with a length of $$$(p+1)$$$ where $$$k_1=1$$$ and $$$k_{p+1}=n+1$$$, such that for every $$$1\le i\le p$$$, the medians of the sequences $$$[a_{k_i},a_{k_i+1},\ldots,a_{k_{i+1}-1}]$$$ are all the same. The parity of $$$k_i$$$ and $$$k_{i+1}$$$ should be different. Your task is to find the biggest possible value of $$$p$$$.

$$$^{\text{∗}}$$$An array $$$b$$$ is a subarray of an array $$$a$$$ if $$$b$$$ can be obtained from $$$a$$$ by the deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.

$$$^{\text{†}}$$$The median of an array with an odd length $$$x$$$ is the $$$\lceil\frac{x}{2}\rceil$$$-th element of the array after it is sorted in non-decreasing order.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 1000$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1\le n \lt 5000$$$, $$$n$$$ is odd) — the length of $$$a$$$.

The second line contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1\le a_i\le 10^9$$$) — the elements of $$$a$$$.

It is guaranteed that the sum of $$$n^2$$$ over all test cases does not exceed $$$5000^2$$$.

Output

For each test case, output a single integer — the maximum number of subarrays.

Note

In the first test case, it is optimal to partition $$$a$$$ into $$$[\underline 3, \underline 3, \underline{2, 4, 3}]$$$.

In the second test case, it is optimal to partition $$$a$$$ into $$$[\underline{9, 5, 7}, \underline 7, \underline{4, 7, 7}]$$$.

In the third test case, since all the elements are the same, you can partition each element into a separate subarray.

Median Partition

Examples