#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ul unsigned ll
#define LL __int128_t
#define db double
#define DB long db
#define pii pair<int, int>
#define fi first
#define se second
#define mkpr make_pair
#define mem(a, x) memset(a, x, sizeof(a))
#define rep(i, l, r) for (int i(l), i##End(r); i <= i##End; i = -~i)
#define per(i, r, l) for (int i(r), i##End(l); i >= i##End; i = ~-i)

template<typename T, typename U> void chkmx(T &a, U b) { if (a < b) a = b; }
template<typename T, typename U> void chkmn(T &a, U b) { if (a > b) a = b; }

constexpr int N = 200005;
constexpr ll mod = 998244353, INF = 0x3f3f3f3f3f3f3f3f;
bool bg;
int n, m;
int a[N];
ll ans;

namespace T123 {
    constexpr int M = 2005;
    ll f[M][M];

    void solve() {
        rep(i, 3, n) rep(j, 1, i - 1) f[i][j] = 0;
        rep(i, 2, n - 1) rep(j, 1, i - 1) {
            chkmx(f[i + 1][j], f[i][j] + (a[i] == a[i + 1] ? a[i + 1] : 0));
            chkmx(f[i + 1][i], f[i][j] + (a[j] == a[i + 1] ? a[j] : 0));
        } ans = 0; rep(j, 1, n - 1) chkmx(ans, f[n][j]);
        printf("%lld\n", ans);
        // #ifdef JYR
        // rep(i, 2, n) rep(j, 1, i - 1) printf("f[%d][%d] = %lld\n", i, j, f[i][j]);
        // #endif
    }
}

namespace T5
{
    ll f[N][15];

    void solve() {
        rep(i, 2, n) rep(j, 1, m) f[i][j] = -INF;
        f[2][a[1]] = 0; rep(i, 2, n - 1) rep(j, 1, m) {
            chkmx(f[i + 1][j], f[i][j] + (a[i] == a[i + 1] ? a[i] : 0));
            chkmx(f[i + 1][a[i]], f[i][j] + (j == a[i + 1] ? j : 0));
        } ans = 0; rep(j, 1, m) chkmx(ans, f[n][j]);
        printf("%lld\n", ans);
        // #ifdef JYR
        // rep(i, 2, n) rep(j, 1, m) printf("f[%d][%d] = %lld\n", i, j, f[i][j]);
        // #endif
    }
} // namespace T5

namespace TAC
{
    constexpr int M = 1000005;
    struct SegTree {
        #define lc (i << 1)
        #define rc (lc | 1)

        ll mx[M << 2], tg[M << 2];

        void chg(int i, ll k) { mx[i] += k, tg[i] += k; }
        void psd(int i) { if (tg[i]) chg(lc, tg[i]), chg(rc, tg[i]), tg[i] = 0; }
        void psu(int i) { mx[i] = max(mx[lc], mx[rc]); }

        void bld(int p, int i = 1, int l = 1, int r = m) {
            mx[i] = (l <= p && p <= r ? 0 : -INF), tg[i] = 0;
            if (l == r) return;
            int mid = l + r >> 1;
            bld(p, lc, l, mid), bld(p, rc, mid + 1, r);
        }

        void mdfA(int L, int R, ll k, int i = 1, int l = 1, int r = m) {
            if (L <= l && r <= R) return chg(i, k);
            int mid = l + r >> 1; psd(i);
            if (L <= mid) mdfA(L, R, k, lc, l, mid);
            if (mid < R) mdfA(L, R, k, rc, mid + 1, r);
            psu(i);
        }

        bool mdfC(int p, ll k, int i = 1, int l = 1, int r = m) {
            if (l == r) { return (mx[i] + p <= k ? (mx[i] = k, 1) : 0); }
            int mid = l + r >> 1; bool res = 0; psd(i);
            if (p <= mid) res = mdfC(p, k, lc, l, mid);
            else res = mdfC(p, k, rc, mid + 1, r);
            return psu(i), res;
        }

        ll qry(int L, int R, int i = 1, int l = 1, int r = m) {
            if (L <= l && r <= R) return mx[i];
            int mid = l + r >> 1; ll res = -INF; psd(i);
            if (L <= mid) chkmx(res, qry(L, R, lc, l, mid));
            if (mid < R) chkmx(res, qry(L, R, rc, mid + 1, r));
            return res;
        }

        // #ifdef JYR
        // void print(int i = 1, int l = 1, int r = m) {
        //     printf("%d [%d %d] | %lld %lld\n", i, l, r, mx[i], tg[i]);
        //     if (l == r) return;
        //     int mid = l + r >> 1; print(lc, l, mid), print(rc, mid + 1, r);
        // }
        // #endif
    } T;

    void solve() {
        T.bld(a[1]);
        // #ifdef JYR
        // T.print();
        // #endif
        rep(i, 2, n - 1) {
            // #ifdef JYR
            // printf("%d: %lld %lld | %lld\n", i, T.qry(1, m), T.qry(a[i + 1], a[i + 1]) + a[i + 1], max(T.qry(1, m), T.qry(a[i + 1], a[i + 1]) + a[i + 1]));
            // #endif
            bool fg = T.mdfC(a[i], max(T.qry(1, m), T.qry(a[i + 1], a[i + 1]) + a[i + 1]));
            if (a[i] == a[i + 1]) {
                T.mdfA(1, m, a[i]);
                if (fg) T.mdfA(a[i], a[i], -a[i]);
            }
            // #ifdef JYR
            // T.print();
            // #endif
        } printf("%lld\n", T.qry(1, m));
    }
} // namespace TAC

void solve() {
    scanf("%d", &n), m = 0;
    rep(i, 1, n) scanf("%d", &a[i]), chkmx(m, a[i]);
    if (n <= 2000) T123::solve();
    else
        if (m <= 10) T5::solve();
    else
        TAC::solve(); // puts("0");
}

void init() {}

bool ed;

int main() {
    freopen("color.in", "r", stdin);
    freopen("color.out", "w", stdout);
    init();
    int _; scanf("%d", &_);
    while (_--) solve();
    return 0;
}