#include <queue>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
char str[1000010];
int num[1000010];
int cnt[30];
int main(){
    int T,n,m,ccc;
    scanf("%d",&T);
    while(T--){
        scanf("%s",str);
        scanf("%d",&ccc);
        int len=strlen(str);
        memset(cnt,0,sizeof(cnt));
        memset(num,0,sizeof(num));
        int t=0,s=0,sum=0;
        while(1){
            while(t<len&&sum<ccc){
                int k=str[t]-'a';
                if(cnt[k]==0){
                    sum++;cnt[k]++;
                    t++;
                }else{
                    cnt[k]++;t++;
                }
            }
            if(sum<ccc) break;
            num[s]=t;
            int kk=str[s]-'a';
            if(--cnt[kk]==0){
                sum--;
            }
            s++;
        }
        long long ans=0;
        for(int i=0;i<len;i++){
            if(num[i]==0) continue;
            int ll=len-num[i]+1;
            ans=(long long)ans+(long long)ll;
        }
        printf("%I64d\n",ans);
    }
    return 0;
}