#include <iostream>
#include <stdio.h>
#include <string.h>

using namespace std;

int t , l , r , cnt[26 + 2];
char s[1000000 + 2];
long long n , k , ans;

int main()
{
    cin >> t;
    while( t-- )
    {
        scanf( "%s" , s );
        cin >> k;
        n = strlen( s );
        memset( cnt , 0 , sizeof( cnt ) );
        ans = l = r = 0;
        for( register int i = 0 ; s[i] ; i++ )
        {
            cnt[ s[i] - 'a' ]++;
            register int tot = 0;
            for( register int i = 0 ; i < 26 ; i++ ) tot += !!cnt[i];
            if( tot >= k )
                while( l <= r )
                {
                    cnt[ s[l] - 'a' ]--;
                    if( !cnt[ s[ l++ ] - 'a' ] ) break;
                }
            ans -= r - l + 1;
            r++;
        }
        cout << n * ( n + 1 ) / 2 + ans << endl;
    }
    return 0;
}