#include <array>
#include <iostream>
#include <queue>

using namespace std;

constexpr int N = 1e5, S = 1.11e6 + 1, A = 26;

int ft[S][A], fc[S], fs[S];
basic_string<int> fv[S];
int fn;

void fins(string s, int i) { int v = 0; for (auto c: s) ++fc[v], fs[v] += i, v = ft[v][c] ?: ft[v][c] = ++fn; ++fc[v], fs[v] += i; fv[v].push_back(i); }

int rt[S][A], curmxl[S], curcnt[S];
priority_queue<int, basic_string<int>> rpq[S];
int rn;

int getcnt(int v, int mxl) {
  if (curmxl[v] > mxl) curmxl[v] = mxl, curcnt[v] = 0;
  while (rpq[v].size() && rpq[v].top() > curmxl[v] + 1) rpq[v].pop();
  while (rpq[v].size() && rpq[v].top() > curmxl[v]) rpq[v].pop(), ++curcnt[v];
  return rpq[v].size() + (curmxl[v] == mxl? 0: curcnt[v]);
}

int where[N];

int rcalc(auto s, auto t, int v, int mnl, int mxl) {
  int res = 0;
  while (s != t) if (auto c = *s++; 1) {
    if (--mnl < 0) res += getcnt(v, mxl) - (rt[v][c]? getcnt(rt[v][c], mxl): 0);
    v = rt[v][c];
    if (!v) return res;
    ++mxl;
  }
  return res + getcnt(v, mxl);
}

string s[N];

void borrow(auto s, auto t, int a, int b, int i) {
  while (s != t) if (auto c = *s++; 1) {
    rpq[a].push(::s[i].size());
    if (!rt[a][c]) { rt[a][c] = rt[b][c]; return; }
    a = rt[a][c], b = rt[b][c];
    if (a == b) return;
  }
  rpq[a].push(::s[i].size());
  where[i] = a;
}

void rins(char c, int v, int i) {
  v = rt[v][c] ?: rt[v][c] = rn++;
  rpq[v].push(s[i].size());
  where[i] = v;
}

int k;
int64_t ans;

array<int, 2> fdfs(int v, int l) {
  int sz = 0, r = -1;
  if (fc[v] == 1) {
    r = rn++;
    int i = fs[v];
    where[i] = r;
    rpq[r].push(s[i].size());
    for (int j = s[i].size(); j-- > l; ) rins(s[i][j], where[i], i);
    if (fv[v].empty()) fv[v] = {i};
    return {1, r};
  }
  if (fv[v].size()) {
    r = rn++;
    int i = fv[v][0];
    where[i] = r;
    rpq[r].push(s[i].size());
    sz = 1;
  }
  for (auto u: ft[v]) if (u) {
    auto [su, ru] = fdfs(u, l + 1);
    for (auto x: fv[u]) rins(s[x][l], where[x], x);
    if (su > sz) swap(su, sz), swap(r, ru), swap(fv[u], fv[v]);
    if (!~ru) continue;
    for (auto i: fv[u]) ans += rcalc(s[i].rbegin(), s[i].rend() - l, r, s[i].size() - l - k, l + k);
    for (auto i: fv[u]) borrow(s[i].rbegin(), s[i].rend() - l, r, ru, i);
    fv[v].insert(fv[v].end(), fv[u].begin(), fv[u].end());
    array{move(fv[u])};
    sz += su;
  }
  return {sz, r};
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  fill(curmxl, end(curmxl), 1e9);
  for (int tc = (cin >> tc, tc); tc--; ) {
    int n; cin >> n >> k;
    fn = 1, rn = 0;
    for (int i = 0; i < n; ++i) {
      cin >> s[i];
      for (auto& c: s[i]) c -= 'A';
      fins(s[i], i);
    }
    fdfs(0, 0);
    cout << ans << '\n';
    ans = 0;
    for (int i = 0; i < fn + 1; ++i) array{move(fv[i])};
    for (int i = 0; i < rn; ++i) array{move(rpq[i])};
    fill(fc, fc + fn + 1, 0);
    fill(fs, fs + fn + 1, 0);
    fill(ft[0], ft[fn + 1], 0);
    fill(rt[0], rt[rn], 0);
    fill(curmxl, curmxl + rn, 1e9);
  }
}