#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#define Maxn 710

#define inf 100000000

using namespace std;

int ri[Maxn][Maxn],le[Maxn][Maxn],n,m;

char str[Maxn];

bool OK(int pos,int x)

{

    int i,j,cnt=inf;

    if(pos==) {

        cnt=min(cnt,ri[pos][x]);

        return cnt<=m;

    }

    for(i=;i<=n;i++){

        if(i>x) break;

        cnt=min(cnt,ri[pos][i]+le[pos-][x-i]);

    }

    //cout<<pos<<" "<<x<<" "<<cnt<<" "<<m<<endl;

    return cnt<=m;

}

int main()

{

    int t,i,j,ze,Ca=;

    scanf("%d",&t);

    while(t--){

        for(i=;i<Maxn;i++){

            for(j=;j<Maxn;j++){

                ri[i][j]=le[i][j]=inf;

            }

        }

        ze=;

        scanf("%d%d%s",&n,&m,str);

        if(str[]=='') le[][]=,ze=;

        for(i=;i<n;i++){

            if(str[i]=='') ze++;

            for(j=;j<=n;j++){

                if(le[i][j-]>=inf) break;

                if(str[i]=='')

                    le[i+][j]=le[i][j]+j;

                else

                    le[i+][j]=le[i][j-];

            }

        }

        if(str[n-]=='') ri[n][]=ri[n+][]=;

        for(i=n-;i>=;i--){

            for(j=;j<=n;j++){

                if(ri[i+][j-]>=inf) break;

                if(str[i-]=='')

                    ri[i][j]=ri[i+][j]+j;

                else

                    ri[i][j]=ri[i+][j-];

            }

        }

        int f=;

        int ans=,l,r,mid;

        for(i=;i<=n;i++){

            if(str[i-]==''){

                l=;r=ze;

                while(l+<r){

                    mid=(l+r)>>;

                    if(OK(i,mid))

                        l=mid;

                    else

                        r=mid;

                }

                ans=max(ans,l);

                if(OK(i,r))

                    ans=max(ans,r);

            }

        }

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

    }

    return ;

}