#include <bits/stdc++.h>
using namespace std;
constexpr double eps = 1e-8;

int n, m;
char a[500005];
double p, l[500005], r[500005], pr[500005], lsh[500005];

#define lowbit(i) (i & -i)


double bit[500005];

void init(int n) { for (int i = 1; i <= n; i++) bit[i] = -1e18; }
void Upt(int k, double x) { for (int i = k; i <= m; i += lowbit(i)) bit[i] = max(bit[i], x); }
double Qry(int k) { double _(-1e18); for (int i = k; i; i -= lowbit(i)) _ = max(_, bit[i]); return _; }

int check(double mid) {
    m = 0;
    for (int i = n; i >= 0; i--) {
        lsh[++m] = l[i] = pr[i] - i * mid, r[i] = pr[i] + i * mid;
    }
    sort(lsh + 1, lsh + m + 1);
    m = unique(lsh + 1, lsh + m + 1) - lsh - 1;
    init(m);
    Upt(lower_bound(lsh + 1, lsh + m + 1, l[n]) - lsh, r[n]);
    int rs(0);
    for (int i = n - 1; i >= 0; i--) {
        int id = lower_bound(lsh + 1, lsh + m + 1, l[i]) - lsh;
        if (Qry(id) >= r[i]) rs = i + 1;
        Upt(id, r[i]);
    }
    return rs;
}
int TT;
void solve() {
    cin >> n >> p >> a + 1;
    for (int i = 1; i <= n; i++) a[i] ^= 48, pr[i] = pr[i - 1] + a[i] - p;
    double l = 0, r = max(1 - p, p);
    while (l + eps < r) {
        double mid((l + r) / 2);
        if (check(mid)) r = mid;
        else l = mid;
    }
    cout << "Case #" << ++TT << ": " << check(r)-1 << '\n';
}

signed main() {
#ifdef LARRIX
    freopen("sample.in", "r", stdin);
    freopen("sample.out", "w", stdout);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int T; cin >> T;
    while (T--) solve();
    return 0;
}
/*
*/