#include"bits/stdc++.h"

using namespace std;
using ll = long long;

struct strhash {
    static constexpr int p[2] = {223333333, 773333333};
    static constexpr int mod[2] = {1000000033, 1000002233};
    int n;
    vector<vector<ll>> h, pw;
    strhash() {}
    strhash(string s): n(s.size()), h(2,vector<ll>(n+1)), pw(h) {
        pw[0][0]=pw[1][0]=1;
        for(int i=1;i<=n;++i) pw[0][i]=pw[0][i-1]*p[0]%mod[0],pw[1][i]=pw[1][i-1]*p[1]%mod[1];
        for(int i=1;i<=n;++i) h[0][i]=(h[0][i-1]*p[0]+s[i-1])%mod[0],h[1][i]=(h[1][i-1]*p[1]+s[i-1])%mod[1];
    }
    void init(string s) {
        n = s.size();
        h.resize(2, vector<ll>(n+1));
        pw.resize(2, vector<ll>(n+1));
        pw[0][0]=pw[1][0]=1;
        for(int i=1;i<=n;++i) pw[0][i]=pw[0][i-1]*p[0]%mod[0],pw[1][i]=pw[1][i-1]*p[1]%mod[1];
        for(int i=1;i<=n;++i) h[0][i]=(h[0][i-1]*p[0]+s[i-1])%mod[0],h[1][i]=(h[1][i-1]*p[1]+s[i-1])%mod[1];
    }
  	ll get(int i, int j) {
        assert(0 <= i && i <= j && j < n);
        return (((h[0][j+1]-h[0][i]*pw[0][j-i+1]%mod[0]+mod[0])%mod[0])<<30)
               +(h[1][j+1]-h[1][i]*pw[1][j-i+1]%mod[1]+mod[1])%mod[1];
    }
};

const int maxn = 5e5 + 5;
int tr[maxn][26], id[maxn];

int main() {
    memset(id, -1, sizeof(id));
    int t;
    cin >> t;
    while(t--) {
        int n;
        cin >> n;
        vector<string> s(n);
        for(int i = 0; i < n; ++i) cin >> s[i];
        sort(s.begin(), s.end());
        vector<string> a;
        vector<int> c;

        for(int i = 0, j = 0; i < n; i = j + 1) {
            j = i;
            while(j+1 < n && s[j+1] == s[i]) ++j;
            a.push_back(s[i]);
            c.push_back(j-i+1);
        }

        n = a.size();
        vector<int> sum(n + 1);
        for(int i = 0; i < n; ++i) sum[i+1] = sum[i] + c[i];
        vector<strhash> h(n);
        for(int i = 0; i < n; ++i) h[i].init(a[i]);

        vector<int> pre(n);
        int tot = 0;
        for(int i = 0; i < n; ++i) {
            int p = 0, lst = -1;
            for(char x : a[i]) {
                if(!tr[p][x-'a']) tr[p][x-'a'] = ++tot;
                p=tr[p][x-'a'];
                if(id[p] != -1) lst = id[p];
            }
            id[p] = i;
            pre[i] = lst;
        }

        auto ispre = [&](int i, int j) -> int {
            if(a[j].size() < a[i].size()) return 0;
            int sz = a[i].size();
            return h[i].get(0, sz-1) == h[j].get(0, sz-1);
        };
        auto cmp = [&](int i, int j, int k) {
            int p = a[i].size(), m = min(a[j].size(), a[k].size() - a[i].size());
            int lo = 0, hi = m;
            while(lo < hi) {
                int mid = (lo + hi) / 2;
                if(h[j].get(0, mid) == h[k].get(p, mid + p)) lo = mid + 1;
                else hi = mid;
            }
            if(lo == m) return a[i].size() + a[j].size() > a[k].size();
            assert(a[j][lo] != a[k][lo+p]);
            return a[j][lo] > a[k][lo+p];
        };

        ll ans = 0;
        vector<int> f(n);
        for(int j = 0; j < n; ++j) {
            // (j, j, j)
            ans += 1ll*c[j]*(c[j]-1)*(c[j]-2)/6;
            // (k, j, j), k < j
            ans += 1ll*c[j]*(c[j]-1)/2*sum[j];

            vector<int> l;
            for(int i = pre[j]; i >= 0; i = pre[i]) {
                assert(ispre(i, j));
                // count(i, i, j)
                if(c[i] > 1 && cmp(i, i, j)) ans += 1ll*c[i]*(c[i]-1)/2*c[j];
                // count(k, i, j), k < i < j
                // a[i] + a[k] > a[j]
                // sum k<=p<i c[i]*c[p]*c[j] -> c[i]*c[j]*(sum[i]-sum[k])
                int lo = 0, hi = j;
                while(lo < hi) {
                    int mid = (lo + hi) / 2;
                    if(cmp(i, mid, j)) hi = mid;
                    else lo = mid + 1;
                }
                int sc = sum[j] - sum[lo];
                if(lo <= i) sc -= c[i];
                ans += 1ll * c[i] * c[j] * sc;
                f[i] = lo;
                for(int x : l) {
                    if(f[x] <= i && f[i] <= x) ans -= 1ll * c[i] * c[x] * c[j];
                }
                l.push_back(i);
            }
        }
        cout << ans << '\n';

        memset(tr,0,sizeof(int)*26*(tot+1));
        memset(id,-1,sizeof(int)*(tot+1));
    }
    return 0;
}