//Copyright(c)2016 liuchenrui
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<iostream>
#define LL long long
using namespace std;
inline void splay(int &v){
    v=0;char c=0;int p=1;
    while(c<'0' || c>'9'){if(c=='-')p=-1;c=getchar();}
    while(c>='0' && c<='9'){v=(v<<3)+(v<<1)+c-'0';c=getchar();}
    v*=p;
}
char s[1000010];
int t[66];
int m,tot;
void del(int w){
    if(w==0)return;
    t[s[w]-'a']--;
    if(t[s[w]-'a']==0)tot--;    
}
void add(int w){
    t[s[w]-'a']++;
    if(t[s[w]-'a']==1)tot++;
}
int main(){
    int T;splay(T);
    while(T--){
        memset(t,0,sizeof t);
        scanf("%s%d",s+1,&m);
        int n=strlen(s+1);tot=0;
        int l=1,r=0;
        LL ans=0;
        for(l=1;l<=n;l++){
            del(l-1);
            while(tot<m&&r<=n)add(++r);
            ans+=(LL)n-r+1;
        }
        cout<<ans<<endl;
    }    
}