Beautiful Flip

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define FOR(i , a , b) for(int i = (a);i <= (b);i++)
#define FOD(i , a , b) for(int i = (a);i >= (b);i--)
#define REP(i , n) for(int i = 1;i <= (n);i++)
#define REP0(i , n) for(int i = 0;i < (n);i++)
#define pb push_back
#define printclock cerr<<"\nTime : "<<1000*(double)clock()/(double)CLOCKS_PER_SEC<<"ms\n";
const int mod = 1e9 + 7,inf = 1000111000, mxn = 5e5 + 5;
int n, k, p[mxn];
string s;
inline void maxz(int &a, int b)
{
    if(a < b) a = b;
}
void solve()
{
    cin >> n >> k >> s;
    s = ' ' + s;
    int cnt0 = 0 , cnt1 = 0;
    FOR(i, 1, n)
    {
        int x = (s[i] == '1') ? 1 : -1;
        p[i] = p[i - 1] + x;
        // cout << p[i] << ' ';
        if(s[i] == '1') cnt1++;
        else cnt0++;
    }
    // cout << '\n';
    int all = p[n];

    multiset<int> s;
    s.insert(2 * p[0]);
    int ans = 0;
    ans = max(ans , min(cnt0 , cnt1));
    FOR(i, 1, n)
    {
        if(i > k)
        {
            s.erase(s.find(2 * p[i - k - 1]));
        }
        int x = 2 * p[i] - all;
        auto it = s.lower_bound(x);
        if(it != s.begin()) it--;
        if(it != s.begin()) it--;
        if(it != s.begin()) it--;
        int cnt = 0;
        while(cnt <= 6 && it != s.end())
        {
            int val = *it;
            int y = all + val - 2 * p[i];
            // cout << val / 2 << ' ' << p[i] << '\n';
            // cout << y << '\n';
            y = abs(y);
            int big = (n + y) / 2, small = n - big;
            maxz(ans, small);
            cnt++;
            it++;
        }
        s.insert(2 * p[i]);
    }
    cout << ans << '\n';
}
int32_t main()
{
#define task "cpp"
    if (fopen(task".inp", "r"))
    {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    cin.tie(0)->sync_with_stdio(0);
    int t;
    cin >> t;
    while(t--)
    {
        solve();
    }

    //printclock;
    return 0;
}