#include <stdio.h>

 #include <iostream>

 #include <stdlib.h>

 #include <algorithm>

 #include <string.h>

 #define N 1000100

 char s[N];

 int vis[N];

 int t;

 int k;

 int main()

 {

     scanf("%d",&t);

     while(t--)

     {

         scanf("%s",s);

         scanf("%d",&k);

         int len=strlen(s);

         memset(vis,,sizeof(vis));//标记字母出现的次数

         long long int cnt=,ans=,len1=-,sum=;

         for(int i=;i<len;i++)

         {

             while(cnt!=k&&len1<len)

             {

                 len1++;

                 if(len1>=len)

                     break;

                     if(vis[s[len1]-'a']==)

                         cnt++;//每有一个不同的那么计数器就加一

                     vis[s[len1]-'a']++;

             }

             if(len1>=len)//枚举完了就跳出

                 break;

                 ans=ans+(len-len1);//如果(i,j)满足这个性质,那么(i,k)(K>=J)都满足这个性质

             if(--vis[s[i]-'a']==)//如果这个满足这个性质的子串里面这个字母只出现了一次，那么这个字母之后肯定是满足不了这个性质的，也就是不同的字母会少一个，就要重新再找一次满足性质的最小的右端点

                     cnt--;

         }

         printf("%lld\n",ans);

     }

     return ;

 }