#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define inf 1000000007
#define N 1000005
using namespace std;
typedef long long ll;
int T,k,i,sum,now,n;
ll ans;
int s[30],a[N];
char st[N];
int main()
{
    scanf("%d",&T);
    while (T--)
    {
        scanf("%s",st+1);
        n=strlen(st+1);
        for (i=1;i<=n;i++)a[i]=st[i]-'a'+1;
        scanf("%d",&k);
        ans=0;now=1;sum=0;
        for (i=1;i<=30;i++)s[i]=0;
        for (i=1;i<=n;i++)
        {
            s[a[i]]++;
            if (s[a[i]]==1)sum++;
            //printf("%d\n",sum);
            while (sum>=k)
            {
                if (sum==k&&s[a[now]]==1)break;
                s[a[now]]--;
                if (s[a[now]]==0)sum--;
                now++;
            }
            if (sum>=k)ans=ans+now;
        }
        printf("%I64d\n",ans);
    }
}