#pragma comment(linker, "/STACK:1024000000,1024000000")#include<cstdio>#include<cstring>#include<cmath>#include<algorithm>#include<vector>#include<map>#include<set>#include<queue>#include<stack>#include<ctime>#include<iostream>using namespace std;typedef long long LL;const double pi=acos(-1.0),eps=1e-10;void File(){    freopen("D:\\in.txt","r",stdin);    freopen("D:\\out.txt","w",stdout);}template <class T>inline void read(T &x){    char c = getchar();    x = 0;    while(!isdigit(c)) c = getchar();    while(isdigit(c))    {        x = x * 10 + c - ‘0‘;        c = getchar();    }}int T,k;char t[30],s[20010];int len,pos[30];int sum0[20010],sum1[20010],sum2[20010],dp[510][20010];int q[20010],f1,f2;bool delete1(int t,int a,int b,int c){    if( dp[t][b]-sum1[b]-b*sum0[c]+b*sum0[b]+sum0[b]+sum2[b] <=        dp[t][a]-sum1[a]-a*sum0[c]+a*sum0[a]+sum0[a]+sum2[a]    ) return 1;    return 0;}bool delete2(int t,int a,int b,int c){    if(       ((dp[t][c]-sum1[c]+c*sum0[c]+sum0[c]+sum2[c])-(dp[t][b]-sum1[b]+b*sum0[b]+sum0[b]+sum2[b]))*(b-a)<=       ((dp[t][b]-sum1[b]+b*sum0[b]+sum0[b]+sum2[b])-(dp[t][a]-sum1[a]+a*sum0[a]+sum0[a]+sum2[a]))*(c-b)    ) return 1;    return 0;}int main(){    scanf("%d",&T); int cas=1;    while(T--)    {        scanf("%s%d%s",t,&k,s);        for(int i=0;t[i];i++) pos[t[i]-‘a‘]=i;                sum0[0]=sum1[0]=sum2[0]=0;        for(int i=0;s[i];i++)        {            if(i>0) sum0[i]=sum0[i-1];            sum0[i]=sum0[i]+pos[s[i]-‘a‘];            if(i>0) sum1[i]=sum1[i-1];            sum1[i]=sum1[i]+i*pos[s[i]-‘a‘];            if(i>0) sum2[i]=sum2[i-1];            sum2[i]=sum2[i]+pos[s[i]-‘a‘]*pos[s[i]-‘a‘];        }        for(int i=0;s[i];i++) dp[1][i]=sum1[i]-sum2[i];        len=strlen(s);        for(int j=2;j<=k;j++)        {            f1=f2=0; q[0]=j-2;            for(int i=j-1;i<len;i++)            {                while(1)                {                    if(f2-f1+1<2) break;                    if(delete1(j-1,q[f1],q[f1+1],i)) f1++;                    else break;                }                dp[j][i]=dp[j-1][q[f1]]+(sum1[i]-sum1[q[f1]])-(q[f1]+1)*(sum0[i]-sum0[q[f1]])-(sum2[i]-sum2[q[f1]]);                while(1)                {                    if(f2-f1+1<2) break;                    if(delete2(j-1,q[f2-1],q[f2],i)) f2--;                    else break;                }                f2++;                q[f2]=i;            }        }        printf("Case %d: %d\n",cas++,dp[k][len-1]);    }    return 0;}