/// Author : Nguyễn Thái Sơn - K18 - KHMT - UIT
/// Training ICPC 2023

#include<bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/trie_policy.hpp>
//#include <ext/rope>

//#pragma GCC optimize("Ofast")
//#pragma GCC optimization("unroll-loops, no-stack-protector")
//#pragma GCC target("avx,avx2,fma")

//using namespace std;
//using namespace __gnu_pbds;
//using namespace __gnu_cxx;

#define fi first
#define se second
#define TASK "test"
#define pb push_back
#define EL cout << endl
#define Ti20_ntson int main()
#define in(x) cout << x << endl
#define all(x) (x).begin(),(x).end()
#define getbit(x, i) (((x) >> (i)) & 1)
#define cntbit(x) __builtin_popcount(x)
#define FOR(i,l,r) for (int i = l; i <= r; i++)
#define FORD(i,l,r) for (int i = l; i >= r; i--)
#define Debug(a,n) for (int i = 1; i <= n; i++) cout << a[i] << " "; cout << endl

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> vii;
typedef unsigned long long ull;
typedef vector<vector<int>> vvi;
int fastMax(int x, int y) { return (((y-x)>>(32-1))&(x^y))^y; }

const int N = 5005;
const int oo = INT_MAX;
const int mod = 1e9 + 7;
const int d4x[4] = {-1, 0, 1, 0} , d4y[4] = {0, 1, 0, -1};
const int d8x[8] = {-1, -1, 0, 1, 1, 1, 0, -1}, d8y[8] = {0, 1, 1, 1, 0, -1, -1, -1};

int n, dp[N][2], cnt[N], Val[N][N], a[N];
vector<int> Store[N];

inline void Read_Input() {
    cin >> n;
    FOR(i, 1, n) {
        int u; cin >> u;
        a[i] = u;
        if (Store[u].size() == 0) Store[u].push_back(0);
        Store[u].push_back(i);
    }
}

inline void Solve() {
    FOR(i, 1, n) {
        set<int, greater<int>> S; S.clear();
        for (int j = i; j <= n; j++) {
            S.erase(cnt[a[j]]);
            ++cnt[a[j]];
            S.insert(cnt[a[j]]);
            int u = *S.begin();
            Val[i][j] = max(0, 2 * u - (j - i + 1));
        }
        for (int j = i; j <= n; j++)
            cnt[a[j]]--;
    }
    int Ans = 0;
    FOR(i, 1, n) {
        int cnt = Store[i].size();
        if (cnt == 0) continue;
        Store[i].push_back(n + 1);
        FOR(j, 0, cnt)
            dp[j][0] = dp[j][1] = -mod;
        dp[0][0] = 1;
        FOR(l, 0, cnt - 1)
            FOR(j, 0, 1) {
                FOR(r, l + 1, cnt) {
                    /// ko lay l + 1
                    int dis = Store[i][r] - Store[i][l];
                    if (r != cnt)
                    dp[r][(j + dis) & 1] = max(dp[r][(j + dis) & 1], dp[l][j] - Val[Store[i][l] + 1][Store[i][r]]);
                    if ((j + dis) & 1) {
                        dp[r][0] = max(dp[r][0], dp[l][j] + 1 - Val[Store[i][l] + 1][Store[i][r] - 1]);
                    }
                }
            }
        Ans = max(Ans, dp[cnt][0]);
    }
    cout << max(Ans - 2, 0) << '\n';
    FOR(i, 1, n)
        Store[i].clear();
}

Ti20_ntson {
//    freopen(TASK".INP","r",stdin);
//    freopen(TASK".OUT","w",stdout);
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int T = 1;
    cin >> T;
    while (T -- ) {
        Read_Input();
        Solve();
    }
}