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

import java.util.*;

public class showdown {
  static class State {
    int len, link;
    HashMap<Character, Integer> next = new HashMap<>();
    long cnt;
    boolean isClone;
  }

  static final int MAXLEN = 1000005;
  static State[] st = new State[MAXLEN * 2];
  static int sz, last;

  static void saInit() {
    for (int i = 0; i < sz; i++) {
      st[i] = null;  // clean old states
    }
    sz = 1;
    last = 0;
    st[0] = new State();
    st[0].len = 0;
    st[0].link = -1;
    st[0].cnt = 0;
    st[0].isClone = false;
    st[0].next.clear();
  }

  static void saExtend(char c) {
    int cur = sz++;
    st[cur] = new State();
    st[cur].len = st[last].len + 1;
    st[cur].cnt = 1;
    st[cur].isClone = false;
    int p = last;
    while (p != -1 && !st[p].next.containsKey(c)) {
      st[p].next.put(c, cur);
      p = st[p].link;
    }
    if (p == -1) {
      st[cur].link = 0;
    } else {
      int q = st[p].next.get(c);
      if (st[p].len + 1 == st[q].len) {
        st[cur].link = q;
      } else {
        int clone = sz++;
        st[clone] = new State();
        st[clone].len = st[p].len + 1;
        st[clone].next = new HashMap<>(st[q].next);
        st[clone].link = st[q].link;
        st[clone].cnt = 0;
        st[clone].isClone = true;
        while (p != -1 && st[p].next.get(c) == q) {
          st[p].next.put(c, clone);
          p = st[p].link;
        }
        st[q].link = st[cur].link = clone;
      }
    }
    last = cur;
  }

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int T = sc.nextInt();
    while (T-- > 0) {
      String s = sc.next();
      int k = sc.nextInt();
      saInit();
      for (char c : s.toCharArray()) saExtend(c);

      Integer[] order = new Integer[sz];
      for (int i = 0; i < sz; i++) order[i] = i;
      Arrays.sort(order, (a, b) -> Integer.compare(st[b].len, st[a].len));

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

      int maxFreq = s.length();
      long[] freqSubstringCounts = new long[maxFreq + 1];

      for (int i = 1; i < sz; i++) {
        int freq = (int) st[i].cnt;
        int lengthDiff = st[i].len - st[st[i].link].len;
        freqSubstringCounts[freq] += lengthDiff;
      }

      long ans = 0;
      for (int f = k; f <= maxFreq; f++) {
        ans += freqSubstringCounts[f];
      }
      System.out.println(ans);
    }
    sc.close();
  }
}