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

using namespace std;

void solve () {
    int n;
    cin >> n;

    string s;
    cin >> s;

    vector <bool> ok (n);
    for (int i = 0; i < n; i ++) {
        if (s[i] == '1') {
            bool ok1 = true, ok2 = true;
            if (i && s[i - 1] == '1') {
                ok1 = false;
            }
            if (i < n - 1 && s[i + 1] == '1') {
                ok2 = false;
            }
            if (ok1 && ok2) {
                ok[i] = true;
            }
        }
    }

    auto check = [&] (int x) {
        vector <int> must (n);
        for (int i = 0; i < n; i ++) {
            if (s[i] == '1') {
                continue;
            }
            int j = i - 1;
            while (j + 1 < n && s[j + 1] == '0') {
                j ++;
            }
            if (i - 1 >= 0) {
                if (! ok[i - 1] || ! must[i - 1]) {
                    if (i + x - 1 >= j) {
                        continue;
                    }
                }
                if (j + 1 >= n) {
                    return i + x - 1 - must[i - 1] >= j;
                }
                if ((i + x - 1 - must[i - 1]) + x < j) {
                    return false;
                }
                if (ok[j + 1] && i + x - 1 - must[i - 1] + x - 1 < j) {
                    must[j + 1] = 1;
                }
            } else {
                if (j - i + 1 > x) {
                    return false;
                }
                if (ok[j + 1] && x - 1 < j - i + 1) {
                    must[j + 1] = 1;
                }
            }
            i = j;
        }
        return true;
    };

    int l = 0, r = n;
 
    while (l < r) {
        int mid = (l + r) / 2;
        if (check (mid)) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }    

    cout << l << '\n';
}

signed main () {
	ios::sync_with_stdio (false);
    cin.tie (nullptr);
    
    int T = 1;
    cin >> T;

    while (T --) {
        solve ();
    }

 	return 0;
}