// Author: Christian Lim
// Date: July 24, 2025

#include <bits/stdc++.h>
using namespace std;

struct State {
  int len, link;
  unordered_map<char, int> next;
  long long cnt;
  bool is_clone;
};

const int MAXLEN = 1000005;
State st[MAXLEN * 2];
int sz, last;

void sa_init() {
  st[0].len = 0;
  st[0].link = -1;
  st[0].next.clear();
  st[0].cnt = 0;
  st[0].is_clone = false;
  sz = 1;
  last = 0;
}

void sa_extend(char c) {
  int cur = sz++;
  st[cur].len = st[last].len + 1;
  st[cur].cnt = 1;
  st[cur].next.clear();
  st[cur].is_clone = false;
  int p = last;
  while (p != -1 && !st[p].next.count(c)) {
    st[p].next[c] = cur;
    p = st[p].link;
  }
  if (p == -1) {
    st[cur].link = 0;
  } else {
    int q = st[p].next[c];
    if (st[p].len + 1 == st[q].len) {
      st[cur].link = q;
    } else {
      int clone = sz++;
      st[clone] = st[q];
      st[clone].len = st[p].len + 1;
      st[clone].cnt = 0;
      st[clone].is_clone = true;
      while (p != -1 && st[p].next[c] == q) {
        st[p].next[c] = clone;
        p = st[p].link;
      }
      st[q].link = st[cur].link = clone;
    }
  }
  last = cur;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int T; cin >> T;
  while (T--) {
    string s; int k; cin >> s >> k;
    sa_init();
    for (char c : s) sa_extend(c);

    vector<int> order(sz);
    iota(order.begin(), order.end(), 0);
    sort(order.begin(), order.end(), [](int a, int b) {
        return st[a].len > st[b].len;
        });

    for (int u : order) {
      if (st[u].link != -1) {
        st[st[u].link].cnt += st[u].cnt;
      }
    }

    int maxFreq = (int)s.size();
    vector<long long> freq_substring_counts(maxFreq + 1, 0);

    // Key fix: add number of substrings (length difference) to freq count directly
    for (int i = 1; i < sz; i++) {
      int freq = (int)st[i].cnt;
      int length_diff = st[i].len - st[st[i].link].len;
      freq_substring_counts[freq] += length_diff;
    }

    long long ans = 0;
    for (int f = k; f <= maxFreq; f++) {
      ans += freq_substring_counts[f];
    }
    cout << ans << "\n";
  }
  return 0;
}
