/**


*/

#include<iostream>
#include<cstring>
#include<cstdio>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn = 17;
const ll Mod = 1e9+7;
const ll inf = 0x3f3f3f3f;
int flag[26];
char s[1000005];
int main()
{
    int T, k;
    cin>>T;
    while(T--)
    {
        memset(flag, 0, sizeof flag);
        int cnt = 0;
        scanf("%s",s);
        scanf("%d",&k);
        int len = strlen(s);
        ll sum = 0;
        int l = 0;
        for(int i = 0; s[i]!='\0'; i++){
            if(flag[s[i]-'a']==0){
                cnt++;
                flag[s[i]-'a']++;
                if(cnt==k){
                    int num = 1;
                    for(int j = l; j<=i; j++){
                        if(flag[s[j]-'a']==1){
                            flag[s[j]-'a'] = 0;
                            cnt--;
                            l = j+1;
                            break;
                        }else
                        {
                            num++;
                            flag[s[j]-'a']--;
                        }

                    }
                    sum += num*(len-i);
                }
            }else
            {
                flag[s[i]-'a']++;
            }
        }
        printf("%I64d\n",sum);
    }
    return 0;
}