#include <bits/stdc++.h>
using namespace std;

class FastReader {
public:
    FastReader() { ios::sync_with_stdio(false); cin.tie(nullptr); }
    int nextInt() { int x; cin >> x; return x; }
    string next() { string s; cin >> s; return s; }
};

class FastWriter {
public:
    void println(long long x) { cout << x << "\n"; }
};

int main() {
    try {
        FastReader in;
        FastWriter out;
        int testcases = in.nextInt();
        
        while (testcases-- > 0) {
            int siz = in.nextInt();
            int ops = in.nextInt();
            string word = in.next();
            priority_queue<long long> pq;
            int curr = 0;
            
            for (char c : word) {
                if (c == '1') {
                    curr++;
                } else {
                    if (curr != 0) pq.push(curr);
                    curr = 0;
                }
            }
            if (curr != 0) pq.push(curr);
            
            while (pq.size() > 1 && ops > 0) {
                long long first = pq.top(); pq.pop();
                long long second = pq.empty() ? 0 : pq.top(); pq.pop();
                pq.push(first + second);
                ops--;
            }
            out.println(pq.top());
        }
    } catch (exception& e) {
        cerr << e.what() << endl;
        return 1;
    }
    return 0;
}