#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define db double
#define gc getchar
#define pb push_back
#define all(x) x.begin(),x.end()
#define y1 __
#define For(i,a,b) for(int i=(a);i<=(b);i++)
#define dFor(i,a,b) for(int i=(a);i>=(b);i--)
#define tomin(x,y) x=min(x,y)
#define tomax(x,y) x=max(x,y)
#define abs_(x) max(x,-(x))
#define eq(x,y) (abs_((x)-(y))<=eps)
#define ull unsigned long long
const int N=5e5+5;
const db eps=1e-9;
int read()
{
	int x=0; int y=1; char c=getchar();
	for(;!isdigit(c);c=getchar()) if(c=='-') y=0;
	for(;isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+(c^48);
	return y?x:-x;
}
char getc() { char c=getchar(); for(;!isdigit(c)&&!isalpha(c);c=getchar()); return c; }

int n;
db p;
char ch[N];
int a[N],sm[N];
db ans;
int as;
struct _N
{
	int x;
	db y;
	bool operator <(_N t)const
	{
		if(eq(y,t.y)) return x<t.x;
		return y<t.y;
	}
}b[N];
db slope(_N x,_N y)
{
	return ((y.y-x.y)/(y.x-x.x));
}
void upd(int x,db y)
{
	if(y<ans-eps||eq(y,ans)&&x<as) as=x,ans=y;
}
void work2()
{
	For(i,1,n) sm[i]=sm[i-1]+a[i];
	For(i,1,n) b[i]=(_N){i,p*i-sm[i]};
	b[0]=(_N){0,0};
	sort(b,b+n+1);
	For(i,0,n-1) if(b[i].x<b[i+1].x) upd(b[i].x+1,slope(b[i],b[i+1]));
}
int work()
{
	scanf("%d%lf",&n,&p);
	scanf("%s",&ch[1]);
	For(i,1,n) a[i]=ch[i]-'0';
	
	ans=2; as=0;
	
	work2();
	For(i,1,n) a[i]^=1;
	p=1-p;
	work2();
	return as-1;
}
int main()
{
//	freopen("tii.in","r",stdin);
//	freopen("tii.out","w",stdout); 
	int T=read();
	For(i,1,T) printf("Case #%d: %d\n",i,work());
//	while(T--) printf("%d\n",work());
	return 0;
}
/*



*/