#include <bits/stdc++.h>
#define ll long long

#define dec double

using namespace std;
const int MAXN = (int)5e5+5;
const dec eps = 1e-7;

int n; char a[MAXN]; dec p, pp;

int pre[MAXN];
dec calc(int l, int r) { return (dec)(pre[r]-pre[l-1])/(r-l+1); }

int l, r; dec now;
void upd(int nl, int nr) {
    dec tmp = calc(nl, nr);
    if (fabs(tmp-pp)<fabs(now-pp) || (fabs(tmp-pp)<fabs(now-pp)+eps&&nl<l)) {
        now=tmp;
        l = nl, r = nr;
    }
}

#define pdi pair<dec,int>

#define mk make_pair

set<pdi> s; map<dec,bool> vis, _;

int main() {
    // g++ code.cpp -o code.exe -std=c++14 -O2 -fno-ms-extensions "-Wl,--stack=1000000000" -DLOCAL; ./code
    time_t stm = clock();

    #ifdef LOCAL
    freopen("data.in", "r", stdin);
    freopen("ans.out", "w", stdout);
    #else
    // freopen("tii.in", "r", stdin);
    // freopen("tii.out", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    #endif

    int Case = 0;
    int T; cin >> T; while (T--) {
        cin >> n >> p >> (a+1);
        if (p > 1.0-eps || (p < 0.5 && p > eps)) {
            p = 1.0-p;
            for (int i = 1; i <= n; i++) {
                a[i] = '0' + ((a[i]-'0')^1);
            }
        }
        pp = p;
        p /= (p-1.0);

        for (int i = 1; i <= n; i++) {
            pre[i]=pre[i-1]+(a[i]=='1');
        }

        now = 2;
        s.clear(); vis = _;
        
        dec pre = 0;
        s.insert(mk(0, 1)); vis[0] = 1;
        for (int i = 1; i <= n; i++) {
            pre += (a[i]=='0'?p:1);

            // printf("->>>>>>>>>>>%d %.2lf\n", i, pre);
            
            auto it = s.upper_bound(mk(pre, i+1));
            // if (it != s.end()) printf("[%d] !%d\n", i, (*it).second);
            if (it != s.end()) upd((*it).second, i); //, puts("A");
            if (it != s.begin()) --it, upd((*it).second, i); //, puts("B");
            // if (it != s.end()) printf("[%d] ?%d\n", i, (*it).second);
            if (!vis[pre]) vis[pre] = 1, s.insert(mk(pre,i+1));

            // printf("LINE %d: \n", i);
            // for (auto it = s.begin(); it != s.end(); it++) {
                // printf("[%.2lf,%d]", (*it).first, (*it).second);
            // } puts("");
        }

        cout << "Case #" << (++Case) << ": " << (l-1) << '\n';
    }

    cerr << "Exec Time: " << (double)(clock()-stm)/CLOCKS_PER_SEC << "s" << endl;
    return 0;
}