#include <cstdio>
#include <cstring>
#include <iostream>

using namespace std;

#define N 1000005

char s[N];
int vis[N], V;
int pr[N];

main() {
  int T, m;
  for (scanf("%d", &T); T --; ) {
    scanf("%s", s + 1);
    scanf("%d", &m);
    int n = strlen(s + 1);
    V ++;
    for (int i = 0; i < 256; i ++) pr[i] = 0;
    long long rlt = 0;
    for (int i = 1, j = 1, cnt = 0; i <= n; i ++) {
      if (j < i) j = i, cnt = 0;
      while (j <= n && cnt < m) {
        if (!pr[s[j]]) cnt ++;
        pr[s[j]] = j;
        j ++;
      }
      if (cnt < m) break;
      rlt += n - j + 2;      
      if (pr[s[i]] == i) pr[s[i]] = 0, cnt --;
    }
    cout << rlt << endl;
  }
}