#include<stdio.h>
#include<string.h>
#define maxn 1111111
char str[maxn];
int main()
{
    int k;
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%s %d",str,&k);
        int i, j;
        int vis[500] = {0};
        int len;
        len = strlen(str);
        int start   = -1;
        int sum = 0;
        long long res = 0;
        for(i=0;i<len;i++)
        {
            
            if(sum<k)
            {
               for(start = start+1;start<len;start++)
               {
                      //printf("%d\n",start);
                  if(vis[str[start]-'a']==0)
                  {
                    sum++;
                  }
                  vis[str[start]-'a']++;
                  if(sum>=k) {break;}
              }
            }
            if(start==len)  break;
            res+=len-start;    
            vis[str[i]-'a']--;
            if(!vis[str[i]-'a']) sum--;
        }
        printf("%I64d\n",res);
    }
    return 0;
}