c++

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int minDaysToInfectAllCities(int n, string& s) {
    int minDays = 0;
    vector<int> infected(n, 0); // 0 represents uninfected, 1 represents infected

    while (true) {
        vector<int> newInfections(n, 0);
        bool newInfection = false;

        for (int i = 0; i < n; i++) {
            if (s[i] == '1' && infected[i] == 0) {
                newInfections[i] = 1;
                if (i > 0) newInfections[i - 1] = 1;
                if (i < n - 1) newInfections[i + 1] = 1;
                newInfection = true;
            }
        }

        if (!newInfection) {
            break; // No new infections in this round
        }

        for (int i = 0; i < n; i++) {
            if (newInfections[i] == 1) {
                infected[i] = 1;
            }
        }

        minDays++;
    }

    return minDays;
}

int main() {
    int T;
    cin >> T;

    while (T--) {
        int n;
        string s;
        cin >> n >> s;

        int result = minDaysToInfectAllCities(n, s);
        cout << result << endl;
    }

    return 0;
}