#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int INF = 1<<30;
char str[1000005];
int next[1000005], h[26], vis[26], A[1000005];
int main() {
    int T; scanf("%d", &T);
    while (T--) {
        scanf("%s", str + 1);
        int K; scanf("%d", &K);
        int n = strlen(str + 1);
        for (int i = 1; i <= n; ++i) next[i] = 0;
        for (int i = 0; i < 26; ++i) { h[i] = 0; vis[i] = 0; }
        for (int i = n; i; --i) {
            next[i] = h[str[i] - 'a'];
            h[str[i] - 'a'] = i;
        }
        int cnt = 0;
        for (int i = 1; i <= n; ++i) {
            if (!vis[str[i] - 'a']) {
                vis[str[i] - 'a'] = 1;
                ++cnt;
            }
            A[i] = cnt;
        }
        A[n + 1] = 27;
        int pos = 1;
        LL ans = 0;
        for (int i = 1; i <= n; ++i) if (!next[i]) next[i] = n + 1;
        for (int l = 1; l <= n && pos <= n; ++l) {
            int L = l, R = next[l] - 1;
            while (A[pos] < K) ++ pos;
            ans += (n - pos + 1);
            for (int i = pos; i <= R; ++i) --A[i];
            while (A[pos] < K) ++ pos;
        }
        printf("%I64d\n", ans);
    }
    return 0;
}