#include <bits/stdc++.h>

using namespace std;
using ll = long long;

auto stupid(vector<string> a) {
    int n = a.size();
    sort(a.begin(), a.end());
    ll res = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
            for (int k = 0; k < j; ++k)res += a[j] + a[k] > a[i] || a[k] + a[j] > a[i];
        }
    }
    return res;
}

using vi = vector<int>;
#define all(c) c.begin(),c.end()
#define sz(c) (int)size(c)
#define rep(i, l, r)for(int i =l;i<r;++i)


struct SuffixArray {
    vi sa, lcp;

    SuffixArray(const vi &s, int lim) {
        int n = sz(s) + 1, k = 0, a, b;
        vi x(all(s)), y(n), ws(max(n, lim)), rank(n);
        x.push_back(0), sa = lcp = y, iota(all(sa), 0);
        for (int j = 0, p = 0; p < n; j = max(1, j * 2), lim = p) {
            p = j, iota(all(y), n - j);
            rep(i, 0, n) if (sa[i] >= j) y[p++] = sa[i] - j;
            fill(all(ws), 0);
            rep(i, 0, n) ws[x[i]]++;
            rep(i, 1, lim) ws[i] += ws[i - 1];
            for (int i = n; i--;) sa[--ws[x[y[i]]]] = y[i];
            swap(x, y), p = 1, x[sa[0]] = 0;
            rep(i, 1, n) a = sa[i - 1], b = sa[i], x[b] =
                        (y[a] == y[b] && y[a + j] == y[b + j]) ? p - 1 : p++;
        }
        rep(i, 1, n) rank[sa[i]] = i;
        for (int i = 0, j; i < n - 1; lcp[rank[i++]] = k)
            for (k &&k--, j = sa[rank[i] - 1];
                    s[i + k] == s[j + k];
        k++);
    }
};

struct node {
    map<int, int> go;
    int pos{-1};
    int cnt{0};
};
vector<node> all;

int create() {
    all.emplace_back();
    return all.size() - 1;
}

struct Fenwick {
    int n;
    vector<int> f;

    Fenwick(int n) : n(n), f(n) {}

    void upd(int i, int x) {
        for (; i < n; i |= i + 1)f[i] += x;
    }

    int get(int i) {
        int res = 0;
        for (; ~i; i &= i + 1, --i)res += f[i];
        return res;
    }

    int sum(int l, int r) {
        return get(r) - get(l - 1);
    }
};

void solve() {
    all.clear();
    int n;
    cin >> n;
    map<vector<int>, int> cnt;
    vector<vector<int>> a(n);
    int st = n + 3;
    for (auto &i: a) {
        string s;
        cin >> s;
        for (auto &c: s) {
            c -= 'a';
            ++c;
            i.push_back((int) c + st);
        }
        cnt[i]++;
    }
    sort(a.begin(), a.end());
    a.resize(unique(a.begin(), a.end()) - a.begin());
    n = a.size();
    vector<int> cz;
    vector<int> pos;
    for (int i = 0; i < n; ++i) {
        pos.push_back(cz.size());
        for (auto x: a[i])cz.push_back(x);
        cz.push_back(i + 1);
    }
    SuffixArray SA(cz, st + 27);
    vector<int> where(cz.size());
    for (int i = 1; i < SA.sa.size(); ++i) {
        where[SA.sa[i]] = i - 1;
    }
    vector<int> pref(n + 1);
    auto sum = [&](int l, int r) {
        if (l > r)return 0;
        return pref[r + 1] - pref[l];
    };
    vector<int> rel(n);
    for (int i = 0; i < n; ++i) {
        rel[i] = where[pos[i]];
        pref[i + 1] = pref[i] + cnt[a[i]];
    }
    int root = create();
    ll res = 0;
    for (int i = 0; i < n; ++i) {
        ll num = cnt[a[i]];
        int cur = root;
        res += num * (num - 1) * (num - 2) / 6;
        res += num * (num - 1) / 2 * sum(0, i - 1);
        int k = a[i].size();
        vector<array<int, 2>> A;
        for (int j = 0; j < k; ++j) {
            int c = a[i][j];
            if (!all[cur].go.count(c))break;
            cur = all[cur].go[c];
            if (~all[cur].pos) {
                A.push_back({all[cur].pos, j + 1});
            }
        }
        vector<int> P(k + 1, -1);
        vector<ll> nu(k + 1);
        cur = root;
        for (int j = 0; j < k; ++j) {
            int c = a[i][j];
            if (!all[cur].go.count(c))break;
            cur = all[cur].go[c];
            auto &[_, p, cn] = all[cur];
            if (!~p) continue;
            nu[j + 1] = cn;
            int it = lower_bound(rel.begin(), rel.end(), where[pos[i] + j + 1]) - rel.begin();
            if (it > i - 1)continue;
            auto g = lower_bound(A.begin(), A.end(), array<int, 2>{it, -1});
            if (g != A.end()) {
                P[j + 1] = (*g)[1];
            }
            ll s = sum(it, i - 1);
            if (it <= p) {
                res += num * cn * (cn - 1) / 2;
                s -= cn;
            }
            res += num * cn * s;
        }
        Fenwick f(k + 1);
        vector<vector<int>> todo(k + 1);
        for (int j = 1; j < k; ++j) {
            if (~P[j])todo[P[j]].push_back(j);
        }
        ll bad = 0;
        for (int j = 1; j < k; ++j) {
            for (auto x: todo[j])f.upd(x, nu[x]);
            if (~P[j]) {
                ll s = f.sum(P[j], k);
                if (P[j] <= j)s -= nu[j];
                bad += nu[j] * s;
            }
        }
        assert(bad % 2 == 0);
        res -= num * (bad / 2);
        cur = root;
        for (auto c: a[i]) {
            if (!all[cur].go.count(c)) {
                all[cur].go[c] = create();
            }
            cur = all[cur].go[c];
        }
        all[cur].cnt = num;
        all[cur].pos = i;
    }
    cout << res << "\n";
}

int main() {
    cin.tie(0)->sync_with_stdio(false);
    int t;
    cin >> t;
    while (t--)solve();
}