#include <algorithm>
#include <cstdlib>
#include <iostream>
#include <set>
#include <memory.h>
#include <stdio.h>
#include <ctime>
//#include <bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 1010;
int num[N], v[N];
char s[1000010];

int main () {
//    freopen ("in.txt", "r", stdin);
    int T;
    cin >> T;
    while (T--) {
        int k;
        scanf ("%s", s);
        cin >> k;
        int len = strlen (s);
        memset (num, 0, sizeof num);
//        cout << s << e
//        memset (v, 0, sizeof v);
        LL res = 0;
        int cnt = 0;
        for (int i = 0, j = 0; i < len; i++) {
            while (j < len && cnt < k) {
//                cout << s[j] << ' ' << num[s[j]] << endl;
                if (!num[s[j]]) {
                    cnt++;
                }
                num[s[j]]++;

                j++;
                if (cnt == k) break;

//                if (n)
            }
//            cout << i << ' '<< j << ' ' << cnt << endl;
            if (cnt >= k) res += len - j + 1;
//            cout << endl << s[i] << ' ' << num[s[i]] << endl;
            num[s[i]]--;
            if (!num[s[i]]) cnt--;
//            cout << num[s[i]] << endl;
//            cout << i << ' '<< j << ' ' << cnt << endl;
//            res +=
        }
        cout << res << endl;
    }
}