#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>

using namespace std;

inline int read()
{
    int x=0, f=0; char ch=getchar();
    while (ch<'0' || ch>'9') f|=(ch=='-'), ch=getchar();
    while ('0'<=ch && ch<='9') x=x*10+ch-'0', ch=getchar();
    return f?-x:x;
}

typedef long long ll;
typedef pair<int,int> Pii;

#define rep(i, l, r) for(int i=l; i<=r; i++)
#define    dow(i, l, r) for(int i=l; i>=r; i--)
#define travel(x) for(edge *p=fir[x]; p; p=p->n)
#define clr(x,c) memset(x, c, sizeof(x))

#define pb push_back
#define all(x) (x).begin(),(x).end()

#define maxn 1000009

int n, K, c[26], now; ll A;
char s[maxn];

int main()
{
    int t=read(); while (t--)
    {
        scanf("%s", s); n=strlen(s); K=read(); clr(c,0); now=0; A=0;
        int l=1; rep(r, 1, n)
        {
            if (!c[s[r-1]-'a']++) now++;
            while (now>=K) if (!--c[s[l++-1]-'a']) now--;
            A+=l-1;
        }
        printf("%lld\n", A);
    }
    return 0;
}