#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N = 1000010;
char str[N];
int a[300];

int main(void)
{
    long long ans;
    int k,t;
    scanf("%d",&t);
    while(t--)
    {
         memset(a, 0, sizeof(a));
         scanf("%s",str);
           scanf("%d",&k);
        ans = 0;
        int len = strlen(str);
        int r = -1;
        int cnt = 0;
        for(int i = 0; i < len ; i++)
        {
            while(cnt < k && r < len)
            {
                r++;
                if( !a[ str[r] ] )
                {
                    cnt++;
                }
                a[ str[r] ]++;
            }
            if(r >= len) break;
//            cout << "i=" << i << "\tr=" << r << endl;
            ans += len-r;
            a[ str[i] ]--;
            if( !a[ str[i] ] ) cnt--;
        }
        printf("%I64d\n",ans);
       // cout << ans << endl;
    }
    return 0;
}