#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define LL long long
using namespace std;
LL gs[30], K;
char s[1100000]; LL len;
int main (){
    LL i, j, k, T;
    scanf ( "%I64d", &T );
    while ( T -- ){
        scanf ( "%s", s+1 );
        len = strlen (s+1);
        scanf ( "%I64d", &K );
        i = 1; j = 1;
        memset ( gs, 0, sizeof (gs) );
        LL ans = 0, sum = 0;
        while ( i <= len && j <= len ){
            if ( sum < K ){
                LL k = s[j]-'a'+1;
                if ( gs[k] == 0 ) sum ++;
                gs[k] ++;
                j ++;
            }
            else {
                ans += (len-j+2);
                LL k = s[i]-'a'+1;
                gs[k] --;
                if ( gs[k] == 0 ) sum --;
                i ++;
            }
        }
        for ( ; i <= len; i ++ ) {
            if ( sum >= K ){
                ans += (len-j+2);
                LL k = s[i]-'a'+1;
                gs[k] --;
                if ( gs[k] == 0 ) sum --;
            }
        }
        printf ( "%I64d\n", ans );
    }
    return 0;
}