#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
char s[1000100];
int t[1000100];
//int vis[100010][26];
int T,k;
int main()
{
    cin>>T;
    while(T--)
    {
        memset(s,0,sizeof(s));
        memset(t,-1,sizeof(t));
        scanf("%s",s);
        scanf("%d",&k);
        int len=strlen(s);
        int maxlen=k-1,st=0,buf=0;
        long long int ans=0;
        int vis[26],j;
        int last[26];
        memset(vis,0,sizeof(vis));
        memset(last,0,sizeof(last));
        for(int i=0;i<len;i++)
        {
            for(j=st;j<len;j++)
            {
                if(buf==k)
                {
                    t[i]=j;
                    break;
                }
                if(vis[ s[j]-'a' ]==0)
                {
                    vis[ s[j]-'a' ]=1;
                    buf++;
                }
                last[ s[j]-'a' ]=j;
                if(buf==k)
                {
                    maxlen=max(maxlen,j);
                    t[i]=j;
                    break;
                }
            }
            if(j==len&&buf!=k) break;
            st=maxlen;
            if(last[s[i]-'a']==i)
            {
                vis[s[i]-'a']=0;
                st++;
                buf--;
            }
            //cout<<t[i]<<' ';
            if(t[i]!=-1) ans+=len-j;
        }
        cout<<ans<<endl;
    }
}