#pragma GCC optimize("Ofast")

#include "bits/stdc++.h"

#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep1(i, n) for (int i = 1; i < (n); ++i)
#define rep1n(i, n) for (int i = 1; i <= (n); ++i)
#define repr(i, n) for (int i = (n) - 1; i >= 0; --i)
#define pb push_back
#define eb emplace_back
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define each(x, a) for (auto &x : a)
#define ar array
#define vec vector
#define range(i, n) rep(i, n)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using ld = long double;
using str = string;
using pi = pair<int, int>;
using pl = pair<ll, ll>;

using vi = vector<int>;
using vl = vector<ll>;
using vpi = vector<pair<int, int>>;
using vvi = vector<vi>;

int Bit(int mask, int b) { return (mask >> b) & 1; }

template<class T>
bool ckmin(T &a, const T &b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
bool ckmax(T &a, const T &b) {
    if (b > a) {
        a = b;
        return true;
    }
    return false;
}

// [l, r)
template<typename T, typename F>
T FindFirstTrue(T l, T r, const F &predicat) {
    --l;
    while (r - l > 1) {
        T mid = l + (r - l) / 2;
        if (predicat(mid)) {
            r = mid;
        } else {
            l = mid;
        }
    }
    return r;
}


template<typename T, typename F>
T FindLastFalse(T l, T r, const F &predicat) {
    return FindFirstTrue(l, r, predicat) - 1;
}


const ll INF = 2e18;
const int INFi = 1e9;
const int N = 30 + 5;
const int LG = 20;

struct suffix_array {
    std::vector<int> order, suffix_position, lcp;

    template<typename T>
    suffix_array(T str = T()) {
        str.push_back(*std::min_element(str.begin(), str.end()) - 1);
        int n = str.size();

        order.resize(n);
        std::iota(order.begin(), order.end(), 0);
        std::sort(order.begin(), order.end(), [&](const int i, const int j) {
            return str[i] < str[j];
        });

        suffix_position.resize(n);
        for (int i = 0; i < n; i++)
            suffix_position[order[i]] = i == 0 ? 0 : suffix_position[order[i - 1]] + (str[order[i]] != str[order[i - 1]]);

        std::vector<int> ptr(n), new_order(n), new_suffix_positoin(n);
        for (int len = 1; suffix_position[order.back()] != n - 1; len <<= 1) {
            std::fill(ptr.begin(), ptr.begin() + suffix_position[order.back()] + 1, 0);
            for (int i = 0; i < n; i++)
                if (suffix_position[i] + 1 < n)
                    ptr[suffix_position[i] + 1]++;

            for (int i = 1; i <= suffix_position[order.back()]; i++)
                ptr[i] += ptr[i - 1];

            for (const int position : order) {
                int suffix = (position - len + n) % n;
                new_order[ptr[suffix_position[suffix]]++] = suffix;
            }
            std::swap(order, new_order);

            for (int i = 0; i < n; i++)
                new_suffix_positoin[order[i]] = i == 0 ? 0 : new_suffix_positoin[order[i - 1]]
                                                             + (suffix_position[order[i]] != suffix_position[order[i - 1]]
                                                                || suffix_position[(order[i] + len) % n] != suffix_position[(order[i - 1] + len) % n]);

            std::swap(suffix_position, new_suffix_positoin);
        }
        assert(order[0] == n - 1);

        lcp.resize(n);
        int current_lcp = 0;
        for (int suffix = 0; suffix < n - 1; suffix++, current_lcp = current_lcp == 0 ? 0 : current_lcp - 1) {
            int previous_suffix = order[suffix_position[suffix] - 1];
            while (str[suffix + current_lcp] == str[previous_suffix + current_lcp])
                current_lcp++;

            lcp[suffix_position[suffix]] = current_lcp;
        }
    }
};


const int SZ = 26;
struct Trie {
    struct node {
        node* nxt[SZ], *parent;
        std::vector<int> ends;
        int parent_index, depth;
        node* suffix_link, *supper_suffix_link;

        node() : parent(nullptr), parent_index(-1), depth(0), suffix_link(nullptr), supper_suffix_link(nullptr) {
            std::fill(std::begin(nxt), std::end(nxt), nullptr);
        }

        bool is_terminal() const {
            return !ends.empty();
        }

        node* go_ignoring_extra_edges(int index) const {
            node* v = nxt[index];
            return v && v->depth == depth + 1 ? v : nullptr;
        }
    };

    node* root;

    Trie() : root(new node()) {}

    template<typename U>
    node* add(const U &str, int id = -1) {
        node* v = root;
        for (int i = 0; i < int(str.size()); i++) {
            int cur_index = str[i] - 'a';
            if (!v->nxt[cur_index]) {
                v->nxt[cur_index] = new node();
                v->nxt[cur_index]->parent = v;
                v->nxt[cur_index]->parent_index = cur_index;
                v->nxt[cur_index]->depth = v->depth + 1;
            }
            v = v->nxt[cur_index];
        }
        if (id != -1)
            v->ends.push_back(id);

        return v;
    }

    node* go(node* v, char c) {
        int cur_index = c - 'a';
        return v->nxt[cur_index];
    }


    std::vector<node*> get_vertices() {
        std::vector<node*> vertices{root};
        for (int i = 0; i < int(vertices.size()); i++)
            for (int j = 0; j < SZ; j++) {
                auto vertex = vertices[i]->go_ignoring_extra_edges(j);
                if (vertex)
                    vertices.push_back(vertex);
            }

        return vertices;
    }

    ~Trie() {
        for (auto vertex : get_vertices())
            delete vertex;
    }
};

template<typename T>
std::vector<int> z_function(const T &str) {
    int n = int(str.size());
    std::vector<int> z(n);
    for (int i = 1, l = 0, r = 0; i < n; i++) {
        if (i < r)
            z[i] = std::min(r - i, z[i - l]);

        while (i + z[i] < n && str[z[i]] == str[i + z[i]])
            z[i]++;

        if (i + z[i] > r)
            l = i, r = i + z[i];
    }
    return z;
}



struct fenwick {
    int n{};
    vector<ll> fenw{};

    void build(int k) {
        n = k;
        fenw.resize(n);
    }

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

    ll get(int i) {
        ll res = 0;
        for (; i >= 0; i = (i & (i + 1)) - 1) res += fenw[i];
        return res;
    }

    ll get(int l, int r) {
        if (l > r) return 0;
        return get(r) - get(l - 1);
    }
};

void solve() {
    int n; cin >> n;
    vector<string> s(n);
    rep(i, n) cin >> s[i];
    sort(all(s));
    vi total;
    vi start(n);
    Trie T;
    rep(i, n) {
        start[i] = total.size();
        for(auto &c : s[i]) total.push_back((int)c + n + 10);
        total.push_back(i);
        T.add(s[i], i);
    }
    suffix_array SA(total);
    vi pos(n);
    rep(i, n) pos[i] = SA.suffix_position[start[i]];
    ll ans = 0;
    rep(i, n) {
        Trie::node* v = T.root;
        ll was = 0;
        auto z = z_function(s[i]);
        z.push_back(0);
        vector<ll> cnt(s[i].size() + 1);
        vector<pair<int, int>> w(s[i].size() + 1, {-1, -1});
        vector<vi> add(s[i].size() + 1);
        fenwick f;
        f.build(s[i].size() + 1);

        for(int p = 1; p < s[i].size(); ++p) {
            if (z[p] == (int)s[i].size() - p) {
                w[p] = {z[p] + 1, s[i].size()};
            } else if (p + z[p] < (int)s[i].size() && s[i][p + z[p]] < s[i][z[p]]) {
                w[p] = {z[p] + 1, s[i].size()};
            }
            if (w[p].first != -1) {
                add[max(w[p].first, p + 1)].push_back(p);
            }
            for(auto &j : add[p]) f.upd(j, cnt[j] - cnt[j - 1]);

            cnt[p] = cnt[p - 1];
            v = T.go(v, s[i][p - 1]);
            if (v->ends.empty()) continue;
            int l1 = v->ends.front();
            int l2 = v->ends.back();
            int sz = v->ends.size();
            cnt[p] += sz;
            assert(l1 <= l2 && l2 < i);
            assert(sz == (l2 - l1 + 1));
            { // a
                int suf_pos = SA.suffix_position[start[i] + p];
                int rq = pos[i];
                int lq = max(pos[l1], suf_pos);

                int nxt = lower_bound(all(pos), lq) - pos.begin();
                assert(nxt >= l1);
                if (nxt < i) {
                    was += sz;
                    ans += 1ll * sz * (i - max(nxt, l2 + 1));
                }
                if (nxt == l1) {
                    ans += 1ll * sz * (sz - 1) / 2;
                }
            }
            { // b
                int suf_pos = SA.suffix_position[start[i] + p];
                int rq = pos[l2];
                int lq = suf_pos;

                int nxt = lower_bound(all(pos), lq) - pos.begin();
                if (nxt <= l2) {
                    assert(nxt <= l1);
                    ans += 1ll * sz * (l1 - nxt);
                }
            }
            if (w[p].first < p && w[p].first != -1) {
                ans -= f.get(w[p].first, p - 1) * sz;
            }
        }
        {
            v = T.go(v, s[i].back());
            int l = v->ends[0];
            int sz = i - l;
            ans += 1ll * sz * (l - was);
            ans += 1ll * sz * (sz - 1) / 2;
        }
    }
    cout << ans << '\n';
}


signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout << setprecision(12) << fixed;
    int t = 1;
    cin >> t;
    rep(i, t) {
        solve();
    }
    return 0;
}