#include <bits/stdc++.h>
using namespace std;
namespace Wilson_Inversion {
    void main();
}
int main() {
    return Wilson_Inversion::main(), 0;
}
namespace Wilson_Inversion {

#define int long long

const int N = 400010;

int n, a[N], rk[N], sa[N], height[N], buk[N], tmp[N], m, id[N], tot, val[N];

struct qry {
    int r, base;
    qry() {}
    qry(int _r, int _base) : r(_r), base(_base) {}
};

int sta[N], nxt[N];

vector<qry> xw[N];

int tr[N << 2], tag[N << 2];

void clear(int x, int l, int r) {
    tr[x] = 0;
    tag[x] = 0;
    if (l == r) return;
    int mid = (l + r) >> 1;
    clear(x << 1, l, mid);
    clear(x << 1 | 1, mid + 1, r);
}

void pushdown(int x, int l, int r) {
    if (tag[x]) {
        tag[x << 1] = tag[x];
        tag[x << 1 | 1] = tag[x];
        int mid = (l + r) >> 1;
        tr[x << 1] = tag[x] * (mid - l + 1);
        tr[x << 1 | 1] = tag[x] * (r - mid);
        tag[x] = 0;
    }
}

void modify(int x, int l, int r, int L, int R, int v) {
    if (L <= l && r <= R) {
        tag[x] = v;
        tr[x] = v * (r - l + 1);
        return;
    }
    pushdown(x, l, r);
    int mid = (l + r) >> 1;
    if (L <= mid) modify(x << 1, l, mid, L, R, v);
    if (R > mid) modify(x << 1 | 1, mid + 1, r, L, R, v);
    tr[x] = tr[x << 1] + tr[x << 1 | 1];
}

int query(int x, int l, int r, int L, int R) {
    if (L > R) return 0;
    if (L <= l && r <= R) return tr[x];
    pushdown(x, l, r);
    int mid = (l + r) >> 1;
    int res = 0;
    if (L <= mid) res += query(x << 1, l, mid, L, R);
    if (R > mid) res += query(x << 1 | 1, mid + 1, r, L, R);
    return res;
}

void buildsa() {
    int *x = rk, *y = tmp;
    m = n;
    for (int i = 0; i <= m; ++i) buk[i] = 0;
    for (int i = 1; i <= n; ++i) buk[x[i] = a[i]]++;
    for (int i = 2; i <= m; ++i) buk[i] += buk[i - 1];
    for (int i = n; i >= 1; --i) sa[buk[x[i]]--] = i;
    for (int k = 1; k <= n; k <<= 1) {
        int num = 0;
        for (int i = n - k + 1; i <= n; ++i) y[++num] = i;
        for (int i = 1; i <= n; ++i) if (sa[i] > k) y[++num] = sa[i] - k;
        for (int i = 1; i <= m; ++i) buk[i] = 0;
        for (int i = 1; i <= n; ++i) buk[x[i]]++;
        for(int i = 2; i <= m; i++) buk[i] += buk[i - 1];
        for(int i = num; i >= 1; i--) sa[buk[x[y[i]]]--] = y[i], y[i] = 0;
        swap(x, y); x[sa[1]] = 1; num = 1;
        for(int i = 2; i <= n; i++)
            x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k]) ? num : ++num;
        m = num;
    }
    for(int i = 1; i <= n; i++) rk[sa[i]] = i;
    for (int i = 1; i <= n; ++i) height[i] = 0;
    for(int i = 1, j = 0; i <= n; height[rk[i++]] = j)
        for(j = j ? j - 1 : j; a[i + j] == a[sa[rk[i] - 1] + j]; j++);
    return;
}

void solve() {
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i], id[i] = i;
    sort(id + 1, id + 1 + n, [&](int x, int y) {return a[x] < a[y];});
    tot = 0;
    for (int j = 1; j <= n; ++j) {
        val[++tot] = a[id[j]];
        a[id[j]] = tot;
        if (j != n && val[tot] == a[id[j + 1]]) --tot;
    }
    buildsa();
    xw[sa[1]].push_back(qry(n, 1));
    for (int i = 2; i <= n; ++i) {
        xw[sa[i]].push_back(qry(n, 1));
        xw[sa[i]].push_back(qry(sa[i] + height[i] - 1, -1));
    }
    int top = 0;
    sta[0] = 0;
    for (int i = n; i; --i) {
        while (top && a[i] >= a[sta[top]]) --top;
        nxt[i] = sta[top];
        sta[++top] = i;
    }
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = i; j != nxt[i - 1]; j = nxt[j]) {
            int t = nxt[j];
            if (!t) t = n + 1;
            modify(1, 1, n, j, t - 1, val[a[j]]);
        }
        // cout << i << " : ";
        for (auto j : xw[i]) {
            ans += j.base * query(1, 1, n, i, j.r);
            // cout << j.r << " " << query(1, 1, n, i, j.r) << '\n';
        }
        // cout << '\n';
    }
    cout << ans << '\n';
    for (int i = 1; i <= n; ++i) xw[i].clear();
    clear(1, 1, n);
    for (int i = 1; i <= n * 2; ++i) rk[i] = 0, sa[i] = 0, height[i] = 0, buk[i] = 0, tmp[i] = 0, id[i] = 0, m = 0, tot = 0, val[i] = 0, sta[i] = 0, nxt[i] = 0, xw[i].clear(), tr[i] = 0, tag[i] = 0;
}

// void sol(int x) {
//     cin >> n;
//     for (int i = 1; i <= n; ++i) cin >> a[i], id[i] = i;
//     if (x > 400) return;
//     sort(id + 1, id + 1 + n, [&](int x, int y) {return a[x] < a[y];});
//     tot = 0;
//     for (int j = 1; j <= n; ++j) {
//         val[++tot] = a[id[j]];
//         a[id[j]] = tot;
//         if (j != n && val[tot] == a[id[j + 1]]) --tot;
//     }
//     buildsa();
//     xw[sa[1]].push_back(qry(n, 1));
//     for (int i = 2; i <= n; ++i) {
//         xw[sa[i]].push_back(qry(n, 1));
//         xw[sa[i]].push_back(qry(sa[i] + height[i] - 1, -1));
//     }
//     int top = 0;
//     sta[0] = 0;
//     for (int i = n; i; --i) {
//         while (top && a[i] >= a[sta[top]]) --top;
//         nxt[i] = sta[top];
//         sta[++top] = i;
//     }
//     int ans = 0;
//     clear(1, 1, n);
//     for (int i = 1; i <= n; ++i) {
//         for (int j = i; j != nxt[i - 1]; j = nxt[j]) {
//             int t = nxt[j];
//             if (!t) t = n + 1;
//             modify(1, 1, n, j, t - 1, val[a[j]]);
//         }
//         // cout << i << " : ";
//         for (auto j : xw[i]) {
//             ans += j.base * query(1, 1, n, i, j.r);
//             // cout << j.r << " " << query(1, 1, n, i, j.r) << '\n';
//         }
//         // cout << '\n';
//     }
//     cout << ans << '\n';
//     for (int i = 1; i <= n; ++i) xw[i].clear();
// }

void main() {
    // freopen("1.in", "r", stdin);
    // freopen("1.out", "w", stdout);
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    int T = 1;
    cin >> T;
    // if (T == 1000) {
    //     while (T--) sol(T);
    //     return;
    // }
    while (T--) solve();
}

}