#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long i64;
const int N = 1e6 + 10;

int main() {

    int tcase;
    scanf("%d", &tcase);
    while (tcase--) {
        int n, k;
        static char s[N];
        static int a[N], tank[N];
        memset(tank, 0, sizeof tank);
        scanf(" %s", s + 1);
        n = strlen(s + 1);
        scanf("%d", &k);
        int l = 1, sum = 0;
        i64 ans = 0;
        for (int i = 1; i <= n; ++i) {
            a[i] = s[i] - 'a' + 1;
            if (!tank[a[i]]) ++sum;
            ++tank[a[i]];
            for (; l < i; ++l) {
                if (tank[a[l]] == 1) {
                    if (sum <= k) break;
                    --sum;
                }
                --tank[a[l]];
            }
            if (sum >= k) 
                ans += l;
        }
        printf("%I64d\n", ans);
    }

    return 0;
}