#include <iostream>

#include <cstdio>

#include <cstring>

#define maxn 1666

using namespace std;

int q[maxn],inq[maxn];

char s[maxn];

int n,k,t,head,tail,ans,cas=;

int main()

{

    scanf("%d",&t);

    while (t--)

    {

        scanf("%d%d",&n,&k);

        scanf("%s",s);

        head=,ans=tail=;

        memset(inq,false,sizeof inq);

        for (int i=; s[i]; i++)

        {

            if (inq[int(s[i])]) ans++;

            q[++tail]=int(s[i]);

            if  (tail-head+>k)

            {

                inq[q[head++]]=false;

            }

            for (int j=head; j<=tail; j++) inq[q[j]]=true;

        }

        printf("Case %d: %d\n",++cas,ans);

    }

    return ;

}