#include <iostream>#include <cstring>#include <cstdio>using namespace std;char s[100005];int n,cnt[30],k,T,st;long long ans;int main(){    cin>>T;    cin.get();    while(T--){        scanf("%s",s);        scanf("%d",&k);        memset(cnt,0,sizeof(cnt));        ans=0;        st=0;        n=strlen(s);        for (int i=0;i<n;i++){            cnt[s[i]-‘a‘]++;            while(cnt[s[i]-‘a‘]>k) cnt[s[st++]-‘a‘]--;            ans+=i-st+1;        }        printf("%I64d\n",ans);    }    return 0;}