#include<set>
#include<map>
#include<queue>
#include<stack>
#include<ctime>
#include<cmath>
#include<vector>
#include<string>
#include<bitset>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<climits>
#include<iostream>
#include<algorithm>
#define LL long long
using namespace std;

const LL maxn = 1001000;
const LL maxk = 3000;

char st[maxn];
LL s[maxk],sk;

int main()
{
    LL t,n,k,ret,l,r;
    
    scanf("%I64d",&t);
    while( t-- )
    {
        memset( s,0,sizeof s );
        ret = sk = 0;
        
        scanf("%s",st+1);
        n = strlen( st+1 );
        scanf("%I64d",&k);
        
        l = 1; r = 0;
        for( ;l<=n;l++ )
        {
            for( ;sk < k && r<=n; )
            {
                r++;
                if( s[st[r]] == 0 ) sk++;
                s[st[r]]++;
            }
            if( r > n ) break;
            ret += n-r+1;
            
            if( s[st[l]] == 1 ) sk--;
            s[st[l]]--;
        }
        printf("%I64d\n",ret);
    }
    
    return 0;
}