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


using namespace std;
#define N 1000005

int cnt[30],l,r,k,now,T,len;
char s[N];
long long ans;

int main(){
    scanf("%d",&T);
    while (T--){
        scanf("%s",s);
        scanf("%d",&k);
        len=strlen(s);
        memset(cnt,0,sizeof(cnt));
        l=r=0;
        ans=0;
        cnt[s[l]-'a']=1;now=1;
        do{
            if (now==k){
                ans+=len-r;
                cnt[s[l]-'a']--;
                if (cnt[s[l]-'a']==0) now--;
                l++;
            }
            else{
                r++;
                if (r==len) break;
                cnt[s[r]-'a']++;
                if (cnt[s[r]-'a']==1) now++;
            }
        }while (l<len);
        printf("%I64d\n",ans);
    }
    return 0;
}