#include <iostream>

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <cmath>

#include <algorithm>

#define lll __int64

using namespace std;

#define N 100007

char ss[N];

int cnt[];

int main()

{

    int len,k,i,t;

    scanf("%d",&t);

    while(t--)

    {

        memset(ss,,sizeof(ss));

        memset(cnt,,sizeof(cnt));

        ss[] = '$';

        scanf("%s",ss+);

        len = strlen(ss+);

        scanf("%d",&k);

        int s = ;

        lll ans = ;

        for(i=;i<=len;i++)

        {

            cnt[ss[i]-'a']++;

            if(cnt[ss[i]-'a'] > k)

            {

                while(ss[s] != ss[i])

                    cnt[ss[s]-'a']--, s++;

                cnt[ss[s]-'a']--, s++;

            }

            ans += i-s+;

        }

        printf("%I64d\n",ans);

    }

    return ;

}