#include <bits/stdc++.h>
// #include "../cpp-dump/cpp-dump.hpp"
template <class T>
void chkmin(T &x, const T &y) {
if (x > y) x = y;
}
template <class T>
void chkmax(T &x, const T &y) {
if (x < y) x = y;
}
using ll = long long;
using std::cerr;
struct suffix_array {
std::vector<int> sa, rk;
std::array<std::vector<int>, 20> st;
suffix_array(std::vector<int> a) {
int n = a.size();
sa.resize(n), rk.resize(n * 2, -1);
std::vector<int> tmp(n), cnt(n);
std::iota(sa.begin(), sa.end(), 0);
std::sort(sa.begin(), sa.end(), [&](int x, int y) { return a[x] < a[y]; });
rk[sa[0]] = 0;
for (int i = 1; i < n; i++)
rk[sa[i]] = rk[sa[i - 1]] + (a[sa[i]] != a[sa[i - 1]]);
for (int w = 1;; w <<= 1) {
int l = 0;
for (int i = n - w; i < n; i++) tmp[l++] = i;
for (int i = 0; i < n; i++)
if (sa[i] >= w) tmp[l++] = sa[i] - w;
for (int i = 0; i < n; i++) {
cnt[rk[sa[i]]] = i;
}
for (int i = n - 1; i >= 0; i--) sa[cnt[rk[tmp[i]]]--] = tmp[i];
tmp[sa[0]] = 0;
for (int i = 1; i < n; i++)
tmp[sa[i]] = tmp[sa[i - 1]] + (rk[sa[i - 1]] != rk[sa[i]] ||
rk[sa[i - 1] + w] != rk[sa[i] + w]);
std::copy_n(tmp.begin(), n, rk.begin());
if (rk[sa[n - 1]] == n - 1) break;
}
st[0].resize(n), rk.resize(n), a.push_back(-1);
for (int i = 0, k = 0; i < n; i++) {
if (k) k--;
if (rk[i] == 0) continue;
while (a[i + k] == a[sa[rk[i] - 1] + k]) k++;
st[0][rk[i]] = k;
}
for (int i = 1; i < 20; i++) {
st[i].resize(n);
for (int j = 0; j + (1 << i) - 1 < n; j++)
st[i][j] = std::min(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
}
}
int lcp(int i, int j) {
if (i == j) return (int)sa.size() - i;
i = rk[i], j = rk[j];
if (i > j) std::swap(i, j);
i++;
int k = std::__lg(j - i + 1);
return std::min(st[k][i], st[k][j - (1 << k) + 1]);
}
};
void mian() {
int n;
std::cin >> n;
std::vector<std::string> s(n);
std::vector<int> ve, idx(n), len(n);
for (int i = 0; i < n; i++) {
std::cin >> s[i];
ve.push_back(1e9 + i), idx[i] = ve.size();
for (char c : s[i]) ve.push_back(c);
len[i] = s[i].size(), s[i].push_back('-');
}
suffix_array sa(ve);
auto cmp = [&](int i, int j, int p = 0) {
if (i == j && !p) return !!0;
int l = sa.lcp(idx[i] + p, idx[j]);
return s[i][l + p] < s[j][l];
};
auto cmp2 = [&](int c, std::pair<int, int> d) { // c < a + b
auto [a, b] = d;
if (a == c) return !!1;
if (sa.lcp(idx[a], idx[c]) == len[a]) return cmp(c, b, len[a]);
return cmp(c, a);
};
std::vector<int> id(n);
std::iota(id.begin(), id.end(), 0);
std::sort(id.begin(), id.end(), cmp);
// cpp_dump(id);
auto find = [&](int i) -> std::pair<int, int> {
auto p = std::upper_bound(id.begin(), id.end(), i, cmp) - id.begin();
int l = len[i];
if (p == n || sa.lcp(idx[id[p]], idx[i]) != l) return std::make_pair(p, p - 1);
int pp = p;
for (int j = 20; ~j; j--) {
if (pp + (1 << j) < n && sa.lcp(idx[id[pp + (1 << j)]], idx[i]) == l)
pp += 1 << j;
}
return std::make_pair(p, pp);
};
std::vector<int> uid;
std::unordered_map<std::string, int> mp;
for (int i : id) {
if (mp.count(s[i]))
mp[s[i]] += 1;
else
mp[s[i]] = 1, uid.push_back(i);
}
ll ans = 0;
for (int i : uid) {
if (mp[s[i]] < 2) continue;
auto t =
std::lower_bound(id.begin(), id.end(), std::make_pair(i, i), cmp2) -
id.begin() - mp[s[i]];
ans += (ll)mp[s[i]] * (mp[s[i]] - 1) / 2 * t;
ans += (ll)mp[s[i]] * (mp[s[i]] - 1) * (mp[s[i]] - 2) / 6;
}
std::vector<int> stk;
// cpp_dump(ans);
// return;
std::vector<std::vector<int>> hope(n);
for (int i = 0; i < (int)uid.size(); i++) {
int a = uid[i];
while (stk.size() && sa.lcp(idx[stk.back()], idx[a]) != len[stk.back()])
stk.pop_back();
for (int p : stk) hope[p].push_back(a);
stk.push_back(a);
}
stk.clear();
for (int i = 0; i < (int)uid.size(); i++) {
int a = uid[i];
while (stk.size() && sa.lcp(idx[stk.back()], idx[a]) != len[stk.back()])
stk.pop_back();
for (int b : hope[a]) {
ll c = (ll)mp[s[a]] * mp[s[b]];
cpp_dump(a, b, c);
if (sa.lcp(idx[a], idx[b]) != len[a]) continue;
auto [l1, r1] = find(b);
chkmin<int>(r1, std::max(std::lower_bound(id.begin(), id.end(),
std::make_pair(a, b), cmp2) -
id.begin() - 1,
std::lower_bound(id.begin(), id.end(),
std::make_pair(b, a), cmp2) -
id.begin() - 1));
ans += std::max(r1 - l1 + 1, 0) * c;
auto [l2, r2] = find(a);
chkmax<int>(l2, find(b).second + 1);
chkmin<int>(r2, std::max(std::lower_bound(id.begin(), id.end(),
std::make_pair(a, b), cmp2) -
id.begin() - 1,
std::lower_bound(id.begin(), id.end(),
std::make_pair(b, a), cmp2) -
id.begin() - 1));
// cpp_dump(a, b, l2, r2, cmp2(1, {2, 1}));
ans += std::max(r2 - l2 + 1, 0) * c;
auto [l3, r3] = std::pair<int, int>(
0, std::lower_bound(id.begin(), id.end(), a, cmp) - id.begin() - 1);
chkmax<int>(
l3, std::upper_bound(id.begin(), id.end(), b, [&](auto x, auto y) {
return cmp(x, y, len[a]);
}) - id.begin());
ans += std::max(r3 - l3 + 1, 0) * c;
ans -= (stk.end() - std::upper_bound(
stk.begin(), stk.end(), b,
[&](auto x, auto y) { return cmp(x, y, len[a]); })) * c;
// cpp_dump(stk, ans);
}
for (int j = 0; j < mp[s[a]]; j++) stk.push_back(a);
}
std::cout << ans << '\n';
}
int main() {
std::cin.tie(0)->sync_with_stdio(0);
int t;
std::cin >> t;
while (t--) mian();
}