#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <string>
using namespace std;

typedef long long LL;

const int Max = 1010000;

char str[Max];

int Hash[30];

int main()
{
    int T;

    int n;

    cin>>T;

    while(T--)
    {
        cin>>str;

        int len = strlen(str);

        memset(Hash,0,sizeof(Hash));

        LL ans = 0;

        int k = 0;

        scanf("%d",&n);

        int L = 0,R = 0;

        while(R<len)
        {
            while(k<n&&R<len)
            {
                if(Hash[str[R]-'a'])
                {
                    Hash[str[R]-'a']++;
                }
                else
                {
                    k++;

                    Hash[str[R]-'a']++;
                }
                R++;
            }
            while(L<=R&&k>=n)
            {

                ans+=(len-R+1);
                
                Hash[str[L]-'a']--;

                if(!Hash[str[L]-'a'])
                {
                    k--;
                }
                
                L++;
            }
        }

        cout<<ans<<endl;
    }
    return 0;
}