#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <cstring>
#define maxn 1000007
#define modp 1000000007

typedef long long LL;
typedef unsigned long long ULL;
int n,m,T,tot;
LL K;

using namespace std;

LL qpow(int x, int y)
{
    if (y<=0) return 1;
    LL res=qpow(x,y>>1);
    res*=res;
    if (y&1) res*=x;
    return res;
}

char s[maxn];
int u[26];

int main()
{
    scanf("%d",&T);
    while (T--)
    {
        scanf("%s",s);
        scanf("%d",&tot);
        LL ans=0;
        memset(u,-1,sizeof(u));
        n=strlen(s);
        m=0;
        int l=0;
        for (int i=0;i<n;++i)
        {
            int k=s[i]-'a';
            if (u[k]<0) ++m;
            u[k]=i;
            if (m>=tot) {
                if (m>tot) {
                    --m;
                    int tmp=n+1, ti;
                    for (int j=0;j<26;++j)
                    {
                        if (u[j]>=0&&u[j]<tmp)
                        {
                            tmp=u[j];
                            ti=j;
                        }
                    }
                    l=tmp+1;
                    u[ti]=-1;
                }
                for (;u[s[l]-'a']!=l;++l);
                //printf("%d: %d\n",i,l+1);
                ans+=(LL)(l+1);
            }
        }
        printf("%I64d\n",ans);
    }
    return 0;
}