#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;

using i64 = long long;
using u32 = unsigned int;
using u64 = unsigned long long;

template<typename T> using vec = vector<T>;

const i64 X = 5e10;

struct PreBIT
{
    int n;
    vec<i64> t;
    PreBIT(int _n): n(_n), t(n + 1, -1e18) { }
    
    void add(int x, i64 v)
    {
        for (++x; x <= n; x += x & -x) {
            t[x] = max(t[x], v);
        }
    }
    i64 ask(int x)
    {
        i64 res = -1e18;
        for (; x; x -= x & -x) {
            res = max(res, t[x]);
        }
        return res;
    }
};

struct SufBIT
{
    int n;
    vec<i64> t;
    SufBIT(int _n): n(_n), t(n + 1, 1e18) { }
    
    void add(int x, i64 v)
    {
        for (x = n - x; x <= n; x += x & -x) {
            t[x] = min(t[x], v);
        }
    }
    i64 ask(int x)
    {
        i64 res = 1e18;
        for (x = n - x; x; x -= x & -x) { // ?
            res = min(res, t[x]);
        }
        return res;
    }
};

void solve(int ca)
{
    int n;
    string rdstr;
    cin >> n >> rdstr;
    i64 y = stod(rdstr) * X;
    
    string s;
    cin >> s;
    vec<int> a(n + 1);
    for (int i = 0; i < n; i++) {
        a[i + 1] = a[i] + s[i] - '0';
    }
    
    vec<i64> w(n + 1);
    for (int i = 0; i <= n; i++) {
        w[i] = (i64)y * i - X * a[i];
    }
    vec<i64> val(w);
    sort(val.begin(), val.end());
    val.erase(unique(val.begin(), val.end()), val.end());
    vec<int> pos(n + 1);
    for (int i = 0; i <= n; i++) {
        pos[i] = lower_bound(val.begin(), val.end(), w[i]) - val.begin();
    }
    
    int vs = val.size();
    
    auto check = [&](i64 m) -> bool
    {
        PreBIT pb(vs);
        SufBIT sb(vs);

        sb.add(pos[n], w[n] - m * n);
        pb.add(pos[n], w[n] + m * n);
        for (int l = n - 1; l >= 0; l--) {
            i64 vu = w[l] - m * l, vd = w[l] + m * l;
            if (sb.ask(pos[l]) <= vu || pb.ask(pos[l]) >= vd) {
                return true;
            }
            sb.add(pos[l], vu);
            pb.add(pos[l], vd);
        }
        
        return false;
    };
    
    i64 l = 0, r = X, mid;
    while (l < r) {
        mid = (l + r) >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    PreBIT pb(vs);
    SufBIT sb(vs);
    
    i64 m = l;
    int ml = n;
    sb.add(pos[n], w[n] - m * n);
    pb.add(pos[n], w[n] + m * n);
    for (int l = n - 1; l >= 0; l--) {
        i64 vu = w[l] - m * l, vd = w[l] + m * l;
        if (sb.ask(pos[l]) <= vu || pb.ask(pos[l]) >= vd) {
            ml = l;
        }
        sb.add(pos[l], vu);
        pb.add(pos[l], vd);
    }
    // cout << ml + 1 << '\n';
    cout << "Case #" << ca << ": " << ml << '\n';
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int t;
    cin >> t;
    for (int i = 0; i < t; i++) solve(i + 1);
    return 0;
}