#include<math.h>
#include<stdio.h>
#include<vector>
#include<iostream>
#include<algorithm>
#include<queue>
#include<string.h>
using namespace std;

const int maxn = 1e6+7;

char s[maxn];
int id[maxn], k;

int main()
{
    int T;

    scanf("%d", &T);

    while(T--)
    {
        scanf("%s", s+1);
        scanf("%d", &k);

        memset(id, 0, sizeof(id));

        int L=1, sum=0;
        long long ans=0;

        for(int i=1; s[i]; i++)
        {
            int t = s[i]-'a';

            if(id[t] == 0)
                sum++;
            id[t] += 1;

            while(sum > k || id[ s[L]-'a' ] > 1)
            {
                if( id[ s[L]-'a' ] == 1 )
                    sum -= 1;
                id[ s[L]-'a' ] -= 1;
                L += 1;
            }

            if(sum == k)
                ans += L;
        }

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

    return 0;
}