Median Partition

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∗ with odd lengths and the same median†. 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 k1=1 and kp+1=n+1, such that for every 1≤i≤p, the medians of the sequences [aki,aki+1,…,aki+1−1] are all the same. The parity of ki and ki+1 should be different. Your task is to find the biggest possible value of p.

∗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.

†The median of an array with an odd length x is the ⌈x2⌉-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≤t≤1000). The description of the test cases follows.

The first line of each test case contains a single integer n (1≤n<5000, n is odd) — the length of a.

The second line contains n integers a1,a2,…,an (1≤ai≤109) — the elements of a.

It is guaranteed that the sum of n2 over all test cases does not exceed 50002.

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 [3_,3_,2,4,3_].

In the second test case, it is optimal to partition a into [9,5,7_,7_,4,7,7_].

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

10
5
3 3 2 4 3
7
9 5 7 7 4 7 7
9
1 1 1 1 1 1 1 1 1
1
5
3
1 2 3
3
2 2 2
5
1 2 3 4 5
5
2 1 3 2 2
7
2 2 1 2 3 2 2
9
2 1 2 3 2 1 2 3 2

3
3
9
1
1
3
1
3
5
5