#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define pob pop_back
#define SZ(x) (int)(x.size())
#define all(x) begin(x), end(x)
#ifdef LOCAL
#define HEHE freopen("in.txt", "r", stdin);
#define debug(...) {cerr << #__VA_ARGS__ << " = "; dbg(__VA_ARGS__);}
#else
#define HEHE ios_base::sync_with_stdio(0), cin.tie(0);
#define debug(...) 7122;
#endif
using namespace std;

#define chmax(a, b) (a) = (a) > (b) ? (a) : (b)
#define chmin(a, b) (a) = (a) < (b) ? (a) : (b)

#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
void dbg() { cerr << '\n'; }
template<typename T, typename ...U>
void dbg(T t, U ...u) { cerr << t << ' '; dbg(u...); }

#define int long long
const int MAXN = 6e5 + 5;
struct suffix_array{
    int n, sa[MAXN], nsa[MAXN], cnt[MAXN], tmp[MAXN];
    int rk[MAXN], lcp[MAXN];
    string s;
    void init(string _s) {
        s = _s + "$";
        n = s.size();
        iota(sa, sa + n, 0);
    }
    void countsort(int sz) {
        FOR (i, 0, n - 1) tmp[cnt[i]]++;
        FOR (i, 1, sz - 1) tmp[i] += tmp[i - 1];
        for (int i = n - 1; i >= 0; i--)    
            nsa[--tmp[cnt[sa[i]]]] = sa[i];
        fill(tmp, tmp + sz, 0);
        copy(nsa, nsa + n, sa);
    }
    void build_SA() {
        FOR (i, 0, n - 1) cnt[i] = s[i];
        countsort(128);
        cnt[sa[0]] = 0;
        FOR (i, 1, n - 1) cnt[sa[i]] = cnt[sa[i - 1]] + (s[sa[i]] != s[sa[i - 1]]);
        for (int k = 1; k < n; k <<= 1) {
            int sz = cnt[sa[n - 1]] + 1;
            FOR (i, 0, n - 1) 
                sa[i] = sa[i] >= k ? sa[i] - k : sa[i] - k + n;
            countsort(sz);
            tmp[sa[0]] = 0;
            FOR (i, 1, n - 1) tmp[sa[i]] = tmp[sa[i - 1]] + 
                ((cnt[sa[i]] != cnt[sa[i - 1]]) or (cnt[(sa[i] + k) % n] != cnt[(sa[i - 1] + k) % n]));
            copy(tmp, tmp + n, cnt);
            fill(tmp, tmp + n, 0);
        }
    }
    vector<vector<int>> st;
    void build_lcp() {
        FOR (i, 0, n - 1) rk[sa[i]] = i;
        int curlcp = 0;
        FOR (i, 0, n - 2) {
            while (s[i + curlcp] == s[sa[rk[i] - 1] + curlcp])
                curlcp++;
            lcp[rk[i]] = curlcp;
            curlcp && curlcp--;
        }
        st.assign(n, vector<int>(19, 0));
        FOR (i, 1, n - 1) st[i][0] = lcp[i];
        FOR (j, 1, 18) {
            for (int i = 1; i + (1 << j) <= n; i++) {
                st[i][j] = min(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
            }
        }
    }
    int _lg(int x) {
        return 64 - __builtin_clzll(x) - 1;
    }
    int LCP(int i, int j) { // [i, j]
        if (i > j) swap(i, j);
        if (i == j) return n - sa[i];
        chmin(j, n - 1); chmax(i, 0);
        // min (lcp[i + 1 : j])
        i++; j++;
        // lcp[i, j)
        int lg = _lg(j - i);
        return min(st[i][lg], st[j - (1 << lg)][lg]);
    }
    void solve(int _n, vector<string> _s, vector<int> pos) {
        // FOR (i, 0, n - 1) {
        //     cout << i << ' ' << s.substr(sa[i]) << '\n';
        // }
        int maxlen = 0;
        FOR (i, 0, _n - 1) chmax(maxlen, _s[i].size());
        vector<int> a;
        vector<vector<int>> a1(maxlen + 1);
        FOR (i, 0, _n - 1) {
            a1[SZ(_s[i])].pb(rk[pos[i]]);
            a.pb(rk[pos[i]]);
        }
        sort(all(a));
        FOR (i, 0, maxlen) sort(all(a1[i]));
        map<string, int> sum;
        map<int, int> ap;
        map<string, int> ctt;
        FOR (i, 0, _n - 1) ctt[_s[i]]++;
        FOR (i, 0, _n - 1) ap[i] = ctt[_s[i]];
        int ans = 0;
        FOR (i, 0, _n - 1) {
            int sum2 = 0;
            FOR (len, 1, SZ(_s[i]) - 1) {
                // _s[i] [1: len]
                int l = rk[pos[i]], r = rk[pos[i]];
                for (int j = 18; j >= 0; j--) {
                    if (l >= (1 << j) and LCP(l - (1 << j), rk[pos[i]]) >= len) {
                        l -= 1 << j;
                    }
                }
                int sb = upper_bound(all(a1[len]), r) - lower_bound(all(a1[len]), l);
                int l1 = rk[pos[i] + len], r1 = rk[pos[i]];
                for (int j = 18; j >= 0; j--) {
                    if (l1 + (1 << j) < n and LCP(rk[pos[i] + len], l1 + (1 << j)) >= SZ(_s[i]) + 1 - len) {
                        l1 += 1 << j;
                    }
                } l1++;

                int overlap = 0;
                if (l1 < l) overlap = sb;
                else if (l1 > r) overlap = 0;
                else upper_bound(all(a1[len]), r) - lower_bound(all(a1[len]), l1);

                int sc = max(0ll, (int)(upper_bound(all(a), r1) - a.begin()) - (lower_bound(all(a), l1) - a.begin()));
                if (l1 < rk[pos[i]]) sc -= ap[i];
                ans += sb * sc - overlap;
                sum2 += sb;
                if (sb * sc - overlap != 0) {
                    //debug(_s[i], len, sb, sc, overlap);
                }
            }
            sum[_s[i]] = sum2;
        }
        map<string, int> mp;
        for (string tmp : _s) {
            mp[tmp]++;
        }
        //cout << ans << '\n';
        int ct = 0;
        for (auto [x, y] : mp) {
            ans += y * (y - 1) / 2 * ct;
            ans += y * (y - 1) * (y - 2) / 6;
            ct += y;
        }
        cout << ans << '\n';
    }
} SA;

void solve() {
    int n; cin >> n;
    vector<string> s(n);
    for (auto &i : s) cin >> i;
    sort(all(s));
    vector<int> pos(n);
    string tmp;
    FOR (i, 0, n - 1) {
        pos[i] = tmp.size();
        tmp += s[i];
        if (i != n - 1) tmp += "$";
    }
    SA.init(tmp);
    SA.build_SA();
    SA.build_lcp();
    SA.solve(n, s, pos);
}

signed main() {
    HEHE
    int t; cin >> t;
    while (t--) solve();
}