#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
 
    // Tìm Median M của toàn bộ mảng
    vector<int> sorted_a = a;
    sort(sorted_a.begin(), sorted_a.end());
    int M = sorted_a[n / 2];
 
    // Tạo mảng điều kiện biên
    vector<int> c1(n), c2(n);
    for (int i = 0; i < n; ++i) {
        c1[i] = (a[i] >= M) ? 1 : -1;
        c2[i] = (a[i] <= M) ? 1 : -1;
    }
 
    // Khởi tạo mảng DP
    vector<int> dp(n + 1, -1);
    dp[0] = 0;
 
    // Chuyển trạng thái DP O(N^2)
    for (int i = 1; i <= n; ++i) {
        int s1 = 0, s2 = 0;
        for (int j = i - 1; j >= 0; --j) {
            s1 += c1[j];
            s2 += c2[j];
 
            // Nếu độ dài lẻ và trạng thái trước đó hợp lệ
            if ((i - j) % 2 == 1 && dp[j] != -1) {
                if (s1 > 0 && s2 > 0) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
        }
    }
 
    cout << dp[n] << "\n";
}
 
int main() {
    // Tối ưu I/O cho C++
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    int t;
    if (cin >> t) {
        while (t--) {
            solve();
        }
    }
    return 0;
}

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8YWxnb3JpdGhtPgoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCnZvaWQgc29sdmUoKSB7CiAgICBpbnQgbjsKICAgIGNpbiA+PiBuOwogICAgdmVjdG9yPGludD4gYShuKTsKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgbjsgKytpKSB7CiAgICAgICAgY2luID4+IGFbaV07CiAgICB9CgogICAgLy8gVMOsbSBNZWRpYW4gTSBj4bunYSB0b8OgbiBi4buZIG3huqNuZwogICAgdmVjdG9yPGludD4gc29ydGVkX2EgPSBhOwogICAgc29ydChzb3J0ZWRfYS5iZWdpbigpLCBzb3J0ZWRfYS5lbmQoKSk7CiAgICBpbnQgTSA9IHNvcnRlZF9hW24gLyAyXTsKCiAgICAvLyBU4bqhbyBt4bqjbmcgxJFp4buBdSBraeG7h24gYmnDqm4KICAgIHZlY3RvcjxpbnQ+IGMxKG4pLCBjMihuKTsKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgbjsgKytpKSB7CiAgICAgICAgYzFbaV0gPSAoYVtpXSA+PSBNKSA/IDEgOiAtMTsKICAgICAgICBjMltpXSA9IChhW2ldIDw9IE0pID8gMSA6IC0xOwogICAgfQoKICAgIC8vIEto4bufaSB04bqhbyBt4bqjbmcgRFAKICAgIHZlY3RvcjxpbnQ+IGRwKG4gKyAxLCAtMSk7CiAgICBkcFswXSA9IDA7CgogICAgLy8gQ2h1eeG7g24gdHLhuqFuZyB0aMOhaSBEUCBPKE5eMikKICAgIGZvciAoaW50IGkgPSAxOyBpIDw9IG47ICsraSkgewogICAgICAgIGludCBzMSA9IDAsIHMyID0gMDsKICAgICAgICBmb3IgKGludCBqID0gaSAtIDE7IGogPj0gMDsgLS1qKSB7CiAgICAgICAgICAgIHMxICs9IGMxW2pdOwogICAgICAgICAgICBzMiArPSBjMltqXTsKICAgICAgICAgICAgCiAgICAgICAgICAgIC8vIE7hur91IMSR4buZIGTDoGkgbOG6uyB2w6AgdHLhuqFuZyB0aMOhaSB0csaw4bubYyDEkcOzIGjhu6NwIGzhu4cKICAgICAgICAgICAgaWYgKChpIC0gaikgJSAyID09IDEgJiYgZHBbal0gIT0gLTEpIHsKICAgICAgICAgICAgICAgIGlmIChzMSA+IDAgJiYgczIgPiAwKSB7CiAgICAgICAgICAgICAgICAgICAgZHBbaV0gPSBtYXgoZHBbaV0sIGRwW2pdICsgMSk7CiAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICB9CgogICAgY291dCA8PCBkcFtuXSA8PCAiXG4iOwp9CgppbnQgbWFpbigpIHsKICAgIC8vIFThu5FpIMawdSBJL08gY2hvIEMrKwogICAgaW9zX2Jhc2U6OnN5bmNfd2l0aF9zdGRpbyhmYWxzZSk7CiAgICBjaW4udGllKE5VTEwpOwogICAgCiAgICBpbnQgdDsKICAgIGlmIChjaW4gPj4gdCkgewogICAgICAgIHdoaWxlICh0LS0pIHsKICAgICAgICAgICAgc29sdmUoKTsKICAgICAgICB9CiAgICB9CiAgICByZXR1cm4gMDsKfQ==

MTAKNQozIDMgMiA0IDMKNwo5IDUgNyA3IDQgNyA3CjkKMSAxIDEgMSAxIDEgMSAxIDEKMQo1CjMKMSAyIDMKMwoyIDIgMgo1CjEgMiAzIDQgNQo1CjIgMSAzIDIgMgo3CjIgMiAxIDIgMyAyIDIKOQoyIDEgMiAzIDIgMSAyIDMgMgo=

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