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. 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). For each test case, output a single integer — the maximum number of subarrays. 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 element