#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <vector>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> PII;
#define fi first
#define se second
#define MP make_pair

int read() {
    int v = 0, f = 1;
    char c = getchar();
    while (c < 48 || 57 < c) {if (c == '-') f = -1; c = getchar();}
    while (48 <= c && c <= 57) v = (v << 3) + v + v + c - 48, c = getchar();
    return v * f;
}

char s[1000100];
int k;
int a[1010];
int main() {
    int T = read();
    while (T--) {
        memset(a, 0, sizeof a);
        scanf("%s", s + 1);
        scanf("%d", &k);
        int n = strlen(s + 1);
        int t1 = 1, t2 = 0;
        ll ans = 0;
        for (int i = 1; i <= n; i++) {
            a[s[i] - 'a']++;
            if (a[s[i] - 'a'] == 1) t2++;
            while (t2 >= k) {
                a[s[t1] - 'a']--;
                if (!a[s[t1] - 'a']) t2--;
                t1++;
            }
            ans += t1 - 1;
        }
        printf("%I64d\n", ans);
    }
}