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.