#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;

#define getmid(l,r) ((l) + ((r) - (l)) / 2)
#define MEM(a,b) memset(a,b,sizeof(a))
#define MP(a,b) make_pair(a,b)
#define PB push_back

typedef long long ll;
typedef pair<int,int> pii;
const double eps = 1e-8;
const int INF = (1 << 30) - 1;
const int MAXN = 100010;

int T,k;
char s[1000010];
int num[30];

int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%s",s + 1);
        int len = strlen(s + 1);
        scanf("%d",&k);
        memset(num,0,sizeof(num));
        int l = 1,r = 1;
        num[s[1] - 'a']++;
        int cnt = 1;
        ll ans = 0;
        for(; l <= len; ++l){
            while(cnt < k && r < len){
                r++;
                num[s[r] - 'a']++;
                if(num[s[r] - 'a'] == 1) ++cnt;
            }
            if(cnt >= k) ans += len - r + 1;
            num[s[l] - 'a']--;
            if(num[s[l] - 'a'] == 0) --cnt;
        }
        printf("%I64d\n",ans);
    }
    return 0;
}