#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 1001005
#define ll long long
int n,k,T,x,y,z;
ll ans,s,l,r,m;
char st[N];
int flag[10000];
void add(int x){
    flag[x]++;
    if(flag[x]==1)s++;
}
void del(int x){
    flag[x]--;
    if(flag[x]==0)s--;
}
int main(){
    scanf("%d",&T);
    while(T--){
        memset(flag,0,sizeof(flag));
        l=0;ans=0;s=0;
        r=0;
        scanf("%s",st+1);
        scanf("%d",&k);
        n=strlen(st+1);
        for (r=1;r<=n;r++){
            add(st[r]);
            if(s>=k)break;
        }
        if(s<k)r=n+1;
        m=0;
        l=1;
        del(st[r]);
        for (int i=r;i<=n;i++){
            add(st[i]);
            while(flag[st[l]]>1||s>k){del(st[l]);l++;}
            ans+=(ll)(l-m)*(n-i+1);
            m=l;
        }
        printf("%I64d\n",ans);
    }
}