#pragma comment(linker, "/STACK:102400000,102400000")
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<stack>
#define LL long long
using namespace std;
const int M = 1e6 + 5, INF = 0x3f3f3f3f;
char s[M];
int A[M];
int main() {
    int T;
    scanf("%d",&T);
    while(T--){
        memset(A,0,sizeof(A));
        scanf("%s",s);
        int K;
        scanf("%d",&K);
        int n=strlen(s);
        int r=0,cnt=0;
        LL ans=0;
        //printf("%d\n",n);
        for(int j=0;j<n;j++){
            while(r<n&&cnt<K){
                int t=s[r++]-'a';
                if(A[t]==0) cnt++;
                A[t]++;
            }
            if(cnt>=K){
                //printf("n - r = %d\n",n-r);
                ans+=n-r+1;
            }
            int now=s[j]-'a';
            A[now]--;
            if(A[now]==0) cnt--;
        }
        cout<<ans<<endl;
    }
    return 0;
}