#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int cas,i,k;
char s[1000010];
int a[1010];
int main(){
    scanf("%d",&cas);
    while (cas--){
        memset(a,0,sizeof a);
        scanf("%s",s+1);
        scanf("%d",&k);
        int n=strlen(s+1);
        int tmp=1,now=0;
        long long ans=0;
        for (i=1;i<=n;i++){
            a[s[i]-'a']++;
            if (a[s[i]-'a']==1)now++;
            while (now>=k){
                a[s[tmp]-'a']--;
                if (!a[s[tmp]-'a'])now--;
                tmp++;
            }
            ans+=tmp-1;
        }
        printf("%I64d\n",ans);
    }
}