#include<bits/stdc++.h>
#define LF long double
using namespace std;
const int N=5e5+5;
const LF E=1e-14;
LF P,Ans;
struct Node{int X;LF Y;}B[N];
int n,A[N],S[N],Pl;
inline LF Cal(Node A,Node B){return (B.Y-A.Y)/(B.X-A.X);}
inline void Upd(int x,LF K)
{
	if(K<Ans-E||fabs(Ans-K)<=E&&x<Pl)Pl=x,Ans=K;
}
inline void DP()
{
	for(int i=1;i<=n;i++)
	{
		S[i]=S[i-1]+A[i];
		B[i]={i,P*i-S[i]};
	}
	B[0]={0,0};
	sort(B,B+n+1,[](Node X,Node Y){return X.Y<Y.Y;});
	for(int i=0;i<n;i++)
	{
		if(B[i].X<B[i+1].X)Upd(B[i].X+1,Cal(B[i],B[i+1]));
	}
}
inline int Work()
{
	Ans=1e9,Pl=0;
	scanf("%d%Lf",&n,&P);
	for(int i=1;i<=n;i++)scanf("%1d",&A[i]);
	DP();

	for(int i=1;i<=n;i++)A[i]^=1;
	P=1-P;
	DP();
	return Pl;
}
int main()
{
	int T;scanf("%d",&T);
	for(int i=1;i<=T;i++)printf("Case #%d: %d\n",i,Work()-1);
}