#include <stdio.h>
#include <map>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
#include <string>
#include <cstdlib>
#include <iostream>
#include <cmath>
#include <set>
#include <ctime>
#include <bitset>

#define ll __int64
#define ull unsigned long long
#define MAXN 40010
#define INF 99999999
#define eps 1e-8
#define f_min(a,b) (a<b?a:b)

using namespace std;

int a[30];
char s[1001000];

int main(){
    int T,i,j,x;
    scanf("%d",&T);
    while (T--){
        memset(a,0,sizeof(a));
        scanf("%s%d",s,&x);
        int len=strlen(s);
        int loc=-1,cnt=0;
        ll ans=0;
        for (i=0;i<len;i++){
            if (cnt>=x) ans+=(ll)(len-loc);
            else {
                for (loc=loc+1;loc<len;loc++){
                    int tmp=s[loc]-'a';
                    if (!a[tmp]) cnt++;
                    a[tmp]++;
                    if (cnt>=x) {ans+=(ll)(len-loc);break;}
                }
            }
            a[s[i]-'a']--;
            if (!a[s[i]-'a']) cnt--;

        }
        printf("%I64d\n",ans);
    }
    return 0;
}