#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <iostream>
#include <vector>
using namespace std;

typedef long long ll;
const int INF = 0x3f3f3f3f;
const int N = 1e6 + 100;

int cnt[130];
char s[N];
int main() {
    int _; scanf("%d", &_);
    while(_ --) {

        scanf("%s", s + 1);
        int ls = strlen(s+1);
        int k; scanf("%d", &k);
        ll ans = 0;
        memset(cnt, 0, sizeof cnt);
        int l = 1, r = 1, tot = 0;
        while(r <= ls) {
            if(!cnt[ s[r] ]) tot++;
            cnt[ s[r] ]++;
         //   printf("%d %d %d\n", l, r, tot);
            if(tot >= k) {
                while(l <= r) {
                    if(tot >= k) { ans += (ls - r + 1); cnt[ s[l] ]--; if(cnt[ s[l] ] == 0) tot--; ++l; }
                    else break;
                }
            }
            r++;
        }

        printf("%I64d\n", ans);
    }
    return 0;
}