#include <bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
using std::max; using std::min;
#define INF 1e18
#define rd() read<ll>()
#define lowbit(x) -x & x
#define E(i, l, r) for (int i = l; i <= r; ++ i)
#define FILE(filename) { \
  freopen(#filename ".in", "r", stdin); \
  freopen(#filename ".out", "w", stdout); \
}
template <typename T> inline T read() {
  T x = 0; char c = getchar(); bool f = 0;
  while (c < '0' || c > '9') {if (c == '-') f = 1; c = getchar();}
  while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
  return f ? -x : x;
}
template <typename T> void write(T x) {
  if (x < 0) {putchar('-'); x = -x;}
  if (x / 10) write(x / 10);
  putchar((x % 10) ^ 48);
}
namespace pigeon {
  const int N = 5e5 + 5;
  int n;
  std::string s[N];
  struct strhash {
    int n;
    ull p[2] = {(ull)1e9 + 7, (ull)1e9 + 9};
    std::vector<std::vector<ull> > h, pw;
    strhash() {}
    strhash(std::string s) : n(s.size()), h(2, std::vector<ull>(n + 1)), pw(h) {
      pw[0][0] = pw[1][0] = 1;
      E(i, 1, n) pw[0][i] = pw[0][i - 1] * p[0], pw[1][i] = pw[1][i - 1] * p[1];
      E(i, 1, n) h[0][i] = h[0][i - 1] * p[0] + s[i - 1], h[1][i] = h[1][i - 1] * p[1] + s[i - 1];
    }
    void init(std::string s) {
      n = s.size();
      h.resize(2, std::vector<ull>(n + 1));
      pw.resize(2, std::vector<ull>(n + 1));
      pw[0][0] = pw[1][0] = 1;
      E(i, 1, n) pw[0][i] = pw[0][i - 1] * p[0], pw[1][i] = pw[1][i - 1] * p[1];
      E(i, 1, n) h[0][i] = h[0][i - 1] * p[0] + s[i - 1], h[1][i] = h[1][i - 1] * p[1] + s[i - 1];
    }
    ull get(int i, int j) {
      return ((h[0][j + 1] - h[0][i] * pw[0][j - i + 1]) << 30) + h[1][j + 1] - h[1][i] * pw[1][j - i + 1];
    }
  };
  int tr[N][26], id[N];
  void Main() {
    n = rd();
    std::vector<std::string> s(n);
    E(i, 0, n - 1) std::cin >> s[i];
    std::sort(s.begin(), s.end());
    std::vector<int> c;
    std::vector<std::string> a;
    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();
    std::vector<int> sum(n + 1);
    E(i, 0, n - 1) sum[i + 1] = sum[i] + c[i];
    std::vector<strhash> h(n);
    E(i, 0, n - 1) h[i].init(a[i]);
    std::vector<int> pre(n);
    int idx = 0;
    E(i, 0, n - 1) {
      int p = 0, last = -1;
      for (auto c : a[i]) {
        if (!tr[p][c - 'a'])
          tr[p][c - 'a'] = ++ idx;
        p = tr[p][c - 'a'];
        if (id[p] != -1) last = id[p];
      } id[p] = i; pre[i] = last;
    }
    // E(i, 0, n - 1) std::cout << pre[i] << ' '; puts("");
    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();
      return a[j][lo] > a[k][lo + p];
    };
    ll ans = 0;
    std::vector<int> f(n);
    E(j, 0, n - 1) {
      ans += 1ll * c[j] * (c[j] - 1) * (c[j] - 2) / 6;
      ans += 1ll * c[j] * (c[j] - 1) / 2 * sum[j];
      std::vector<int> l;
      for (int i = pre[j]; i >= 0; i = pre[i]) {
        if (c[i] > 1 && cmp(i, i, j)) ans += 1ll * c[i] * (c[i] - 1) / 2 * c[j];
        int lo = 0, hi = j;
        while (lo < hi) {
          int mid = (lo + hi) >> 1;
          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 (auto x : l)
          if (f[x] <= i && f[i] <= x)
            ans  -= 1ll * c[i] * c[x] * c[j];
        l.push_back(i);
      }
    }
    write(ans); puts("");
    memset(tr, 0, sizeof(int) * 26 * (idx + 1));
    memset(id, -1, sizeof (int) * (idx + 1));
  }
}
int main() {
  int T = rd();
  memset(pigeon::id, -1, sizeof pigeon::id);
  while (T --) pigeon::Main();
  return 0;
}