#include <bits/stdc++.h>
#define For(e,e1,e2) for(int e=(e1);e<=(e2);e++)
#define For_(e,e1,e2) for(int e=(e1);e<(e2);e++)
#define Rof(e,e1,e2) for(int e=(e2);e>=(e1);e--)
#define Rof_(e,e1,e2) for(int e=(e2);e>(e1);e--)
#define exc(e) if(e) continue
#define stop(e) if(e) break
#define ret(e) if(e) return 
#define LL long long
#define ULL unsigned long long
#define DB double
#define cint const int
#define cLL const long long
#define vct vector
#define pb push_back
#define ft first
#define sc second
using namespace std;
void main_init()
{
    
}
cint N=1.02e6;
int n;
char str[N];
int a[N],c[N],h[N],h2[N],fin[N];
DB f,d[N];
pair<DB,int> d_[N]; 
const DB eps=4e-13;
void input()
{
    scanf("%d%lf%s",&n,&f,str+1);
    reverse(str+1,str+n+1);
    a[0]=0; For(i,1,n) a[i]=a[i-1]+(str[i]-'0'); 
}
void Add(int k)
{
    for(int i=k;i<=n;i+=(i&-i))
        c[i]++;
}
int Sum(int k)
{
    int w=0;
    for(int i=k;i;i^=(i&-i))
        w+=c[i];
    return w;
}
void srt(DB w)
{
    For(i,1,n) d_[i]={d[i]=(DB)a[i]-w*i,i};
    sort(d_+1,d_+n+1);
}
bool same(DB w)
{
    For(i,1,n) d[i]=(DB)a[i]-w*i;
    For_(i,1,n) if(d[d_[i].sc]>d[d_[i+1].sc]) return false;
    return true;
}
LL check(DB w)
{
    srt(w);
    For(i,1,n) fin[d_[i].sc]=i;
    For(i,1,n) c[i]=0;
    LL t=0ll;
    For(i,1,n)
    {
        t+=(h[i]=Sum(fin[i]));
        Add(fin[i]);
    }
    return t;
}
int gt(DB w1,DB w2)
{
//  printf("get %.20lf %.20lf\n",w1,w2);
    check(w1); For(i,1,n) h2[i]=h[i];
    check(w2); Rof(i,1,n) if(h[i]!=h2[i]) return i;
    return n;
}
void main_solve()
{
    input();
    DB w1=2.0,w2=-2.0;
    srt(f-eps);
    DB l=f,r=(DB)1.0,mid;
    while(l+eps<r)
        ((same(mid=(l+r)/2.0))?l:r)=mid;
    r+=eps; if(!same(r)) w1=r;
    // printf("r=%lf\n",r);
    srt(f+eps);
    l=(DB)0.0,r=f,mid;
    while(l+eps<r)
        ((same(mid=(l+r)/2.0))?r:l)=mid;
    l-=eps; if(!same(l)) w2=l;
    // printf("l=%lf\n",l);
    DB t=fabs(w1-f)-fabs(w2-f);
    int k;
    if(fabs(t)<=eps*1.5) k=max(gt(f-eps,w1),gt(f+eps,w2));
    else if(t<(DB)0.0) k=gt(f-eps,w1);
    else k=gt(f+eps,w2);
    printf("%d\n",n-k);
}
int main()
{
//  freopen("ex_binary3.in","r",stdin);
    main_init();
    int _; scanf("%d",&_); For(__,1,_)
    {
        printf("Case #%d: ",__);
        main_solve();
    }
    return 0;
}
/*

*/