#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
char str[1000005];
int cnt[30], sum;
long long ans;

int main() {
     int T, k;
     scanf("%d", &T);
     while (T--) {
         memset(cnt, 0, sizeof(cnt));
         scanf("%s%d", str, &k);
         int s=0, t=0, l=strlen(str);
         sum=0;
         ans=0;
         for (;t<l;) {
             int ch;
             while (t<l && sum<k) {
                 ch=str[t++]-'a';
                 if (cnt[ch]==0) {
                     ++sum;
                 }
                 ++cnt[ch];
                 if (sum==k) ans+=l-t+1;
             }
             while (s<t && sum>=k) {
                 ch=str[s++]-'a';
                 --cnt[ch];
                 if (cnt[ch]==0) {
                     --sum;
                 }else ans+=l-t+1;
             }
         }
         printf("%I64d\n", ans);
     }
    return 0;
}