#include <bits/stdc++.h>
using namespace std;

#define int long long

const int N=5e5+5;
const long double eps=1e-12;

int T,n;
long double p;
char s[N];
int a[N];
int sum[N];
struct node
{
    int x;
    long double y;
    bool operator<(const node &T)const{
        if(fabs(y-T.y)<eps)
            return x<T.x;
        return y<T.y;
    }
}b[N];

void solve()
{
    cin>>n>>p;
    cin>>s+1;
    for(int i=1;i<=n;i++) a[i]=s[i]^48;
    for(int i=1;i<=n;i++)
        sum[i]=sum[i-1]+a[i];
    b[n+1]={0,0};
    for(int i=1;i<=n;i++)
        b[i]={i,p*i-sum[i]};
    sort(b+1,b+n+2);
    long double K1=1e14;
    int pos1=n+1;
    for(int i=1;i<=n;i++){
        long double k=(b[i+1].y-b[i].y)/(b[i+1].x-b[i].x);
        if(fabs(k-K1)<eps)
            pos1=min({pos1,b[i].x+1,b[i+1].x+1});
        else if(k<K1&&k>=0){
            K1=k;
            pos1=min(b[i].x+1,b[i+1].x+1);
        }
    }
    // cout<<pos1<<'\n';
    p=1-p;
    for(int i=1;i<=n;i++) a[i]^=1;
    for(int i=1;i<=n;i++)
        sum[i]=sum[i-1]+a[i];
    b[n+1]={0,0};
    for(int i=1;i<=n;i++)
        b[i]={i,p*i-sum[i]};
    sort(b+1,b+n+2);
    long double K2=1e14;
    int pos2=n+1;
    for(int i=1;i<=n;i++){
        long double k=(b[i+1].y-b[i].y)/(b[i+1].x-b[i].x);
        if(fabs(k-K2)<eps)
            pos2=min({pos2,b[i].x+1,b[i+1].x+1});
        else if(k<K2&&k>=0){
            K2=k;
            pos2=min(b[i].x+1,b[i+1].x+1);
        }
    }
    if(fabs(K1-K2)<eps)
        cout<<min(pos1,pos2)-1<<'\n';
    else if(K1<K2)
        cout<<pos1-1<<'\n';
    else
        cout<<pos2-1<<'\n';
}

signed main()
{
    // freopen("tii.in", "r", stdin);
    // freopen("tii.out", "w", stdout);
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>T;
	for(int i=1;i<=T;i++){
		cout<<"Case #"<<i<<": ";
		solve();
	}
    return 0;
}