1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
#include <bits/stdc++.h>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;

    cin >> t;

    while (t--) {
        int n, zera=0, lewy, prawy, dzien, wynik;
        bool czy_byla_jed=0;
        string slowo;
        vector <int> tab;
        
        cin >> n >> slowo;

        for (int i=0; i < n; i++) {
            if (slowo[i] == '1')
                break;
            
            zera++;
        }

        if (zera == n) {
            cout << 0 << '\n';

            return 0;
        }

        lewy = zera;
        zera = 0;

        for (int i=lewy; i < n; i++) {
            if (slowo[i] == '1') {
                if (zera != 0)
                    tab.push_back(zera);

                zera = 0;
            }

            else
                zera++;
        }

        prawy = zera;

        sort(tab.begin(), tab.end(), greater <int>());

        wynik = 0;
        dzien = 0;

        for (int i=0; i < tab.size(); i++) {
            if (lewy - dzien > 0 && lewy - dzien >= tab[i] - (2 * dzien)) {
                wynik += lewy - dzien;
                lewy = 0;
                i--;
                dzien++;
                continue;
            }

            if (prawy - dzien > 0 && prawy - dzien >= tab[i] - (2 * dzien)) {
                wynik += prawy - dzien;
                prawy = 0;
                i--;
                dzien++;
                continue;
            }

            if (tab[i] - (2 * dzien) == 1) {
                wynik += tab[i] - (2 * dzien);
                dzien++;
                continue;
            }

            if (tab[i] - (2 * dzien) - 1 > 0) {
                wynik += tab[i] - (2 * dzien) - 1;
                dzien += 2;
                continue;
            }
        }

        if (lewy - dzien > 0) {
            wynik += lewy - dzien;
            dzien++;
        }

        if (prawy - dzien > 0)
            wynik += prawy - dzien;


        cout << n - wynik << '\n';

        // cout << lewy << ' ';

        // for (int i=0; i < tab.size(); i++)
        //     cout << tab[i] << ' ';

        // cout << prawy << '\n';
    }

    return 0;
}