/*Sherlock and Watson and Adler*/
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<queue>
#include<stack>
#include<math.h>
#include<vector>
#include<map>
#include<deque>
#include<set>
#include<cmath>
#include<complex>
#include<string>
#include<algorithm>
#include<iostream>
#define exp 1e-10
#define ll long long
using namespace std;
const int N =  1000007;
const int M = 10000 + 10;
const int inf = 100000000;
const int mod = 2009;
char s[N];
int vit[30];
int main()
{
    int t,m,k,p,i,j,len,tmp;
    long long sum;
    int n;
    scanf("%d",&t);
    while(t--)
    {
        memset(vit,0,sizeof(vit));
        scanf("%s%d",s,&n);
        len=strlen(s);
        sum=tmp=p=0;
        for(i=0;i<len;i++)
        {
            if(vit[s[i]-'a']==0)
                tmp++;
            vit[s[i]-'a']++;
            if(tmp >= n)
            {
                sum = sum + len - i ;
                for(j=p;j<len;++j)
                {
                    if(vit[s[j]-'a'] == 1)
                        tmp--;
                    vit[s[j]-'a']--;

                    if(tmp < n) break;
                    sum = sum + len - i ;
                }
                p=j+1;
            }
        }
        printf("%I64d",sum);
        puts("");
    }
    return 0;
}