#include <cstdio>
#include <cstdio>
#include <cstring>
#include <cctype>
#include <cmath>
#include <set>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <string>
#include <bitset>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
typedef __int64 LL;
const int maxn = 1e6+10;

char str[maxn];
pair <LL , LL> p[maxn];
LL sign[3000];
LL solve(LL k)
{
    LL u=0;
    memset(sign,0,sizeof(sign));
    LL len;
    len=strlen(str);
    LL l,r;
    l=0;
    r=-1;
    LL now=0;
    LL ans=0;
    while(now<k)
    {
        r++;
        if(r>=len) break;
        if(!sign[str[r]]) now++;
        sign[str[r]]++;
    }
    while(1)
    {
        if(sign[str[l]]>1) l++,sign[str[l-1]]--;
        else break;
    }
    if(now==k) p[u].first=l,p[u++].second=r;
    else return 0;
    while(r<len)
    {
        if(now>=k)
        {
            sign[str[l]]--;
            if(!sign[str[l]])
                now--;
            l++;
            if(l>=len) break;
        }
        else
        {
            r++;
            if(r>=len) break;
            if(!sign[str[r]]) now++;
            sign[str[r]]++;
            if(now==k)
            {
                while(1)
                {
                    if(sign[str[l]]>1) l++,sign[str[l-1]]--;
                    else break;
                }
                p[u].first=l,p[u++].second=r;
            }
        }
    }
    //for(int i=0; i<u; i++) printf("%I64d %I64d \n",p[i].first,p[i].second);
    LL last=p[0].first;
    for(int i=1; i<u; i++)
    {
        ans+=(last+1)*(p[i].second-p[i-1].second);
        last=p[i].first;
    }
    ans+=(last+1)*(len-1-p[u-1].second+1);
    return ans;
}
int main()
{
    LL k,T;
    scanf("%I64d",&T);
    while(T--)
    {
        scanf("%s",str);
        scanf("%I64d",&k);
        printf("%I64d\n",solve(k));
    }
    return 0;
}