#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 1000006;

char s[N];
int cnt[130];

void solve()
{
    int k;
    scanf("%s%d", s, &k);
    long long ans=0;
    int n=strlen(s);
    memset(cnt, 0, sizeof(cnt));
    int p=-1;
    for (int i=0; i<n; ++i) {
        ++cnt[s[i]];
        if (cnt[s[i]] == 1) {
            --k;
        }
        if (k > 0) {
            continue;
        }
        while (k < 1) {
            ++p;
            --cnt[s[p]];
            if (cnt[s[p]] == 0) {
                ++k;
            }
        }
        ++cnt[s[p]];
        --p;
        --k;
        ans += p+2;
    }
    printf("%I64d\n", ans);
}

int main()
{

    int n;
    scanf("%d", &n);
    for (int i=0; i<n; ++i) {
        solve();
    }
    return 0;
}