#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#define LL long long
#define INF 0x3f3f3f3f
using namespace std;
const int maxn = 1e6+100;
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;
}