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

typedef long long LL;

const int maxn=1000010;

char s[maxn];
int cnt[30];

void work(){
    int len;
    scanf("%s",s);
    len=strlen(s);
    memset(cnt,0,sizeof(cnt));
    LL ans=0,cur=0,num=0;
    int k;
    scanf("%d",&k);
    while(cur<len&&num<k){
        ++cnt[s[cur]-'a'];
        if(cnt[s[cur]-'a']==1) ++num;
        ++cur;
    }
    if(num>=k) ans+=len-cur+1;
    for(int i=1; i<len; ++i){
        --cnt[s[i-1]-'a'];
        if(!cnt[s[i-1]-'a']) --num;
        while(cur<len&&num<k){
            ++cnt[s[cur]-'a'];
            if(cnt[s[cur]-'a']==1) ++num;
            ++cur;
        }
        if(num>=k) ans+=len-cur+1;
    }
    cout<<ans<<endl;
}

int main(){
    int kase;
    scanf("%d",&kase);
    while(kase--) work();
    return 0;
}