#include<stdio.h>
#include<algorithm>
#include<string.h>
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
typedef long long LL;
const int Maxn=1000012;
char s[Maxn];
int cur[33];
int k;
int main(){
    int _;scanf("%d",&_);    
    while(_--){
        scanf("%s%d",s,&k);
        for(int i=0;i<26;i++)cur[i]=-1;
        LL ans=0;
        int L=0;
        int tot=0;
        for(int i=0;s[i];i++){
            int tmp=cur[s[i]-'a'];
            cur[s[i]-'a']=i;
            if(tot==k){
                if(tmp<L){
                    L++;
                    while(L<i&&cur[s[L]-'a']!=L)L++;
                }
                else{
                    while(L<i&&cur[s[L]-'a']!=L)L++;
                }
                tot=k;
            }
            else{
                if(tmp<L)tot++;
                while(L<i&&cur[s[L]-'a']!=L)L++;
            }
            if(tot==k)ans+=L+1;
        }
        printf("%I64d\n",ans);
    }
}