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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int findNext(string &s, int start) {
    int x = start;
    while (x < s.length() && s[x] == '0') {
        x++;
    }
    return x;
}

int main() {

    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int t;
    cin >> t;

    for (int it = 0; it < t; it++) {

        int n;
        cin >> n;
        string s;
        cin >> s;

        vector<int> vec;
        vector<int> vec2;

        int x = findNext(s, 0);
        if (x == s.length()) {
            cout << 0 << endl;
            continue;
        }

        int y = s.length() - 1;
        while (s[y] == '0') {
            y--;
        }

        if (x > 0) {
            vec2.push_back(x);
        }
        if (y < s.length() - 1) {
            vec2.push_back(s.length() - y - 1);
        }

        sort(vec2.rbegin(), vec2.rend());

        if (x < y) {

            while (true) {
                int next = findNext(s, x + 1);
                if (next - x > 1) {
                    vec.push_back(next - x - 1);
                }
                if (next == y) {
                    break;
                }
                x = next;
            }

            sort(vec.rbegin(), vec.rend());

            int time = 0;
            int i = 0, j = 0;
            int saved = 0;

            while (i <vec.size() && vec[i] - 2*time > 0 && j <vec2.size() && vec2[j] - time > 0) {

                int avg;
                int ss, d;
                if(vec[i] - 2*time > 2) {
                    avg = vec[i] - 2*time - 1;
                    ss = avg;
                    d = 2;
                } else {
                    ss = 1;
                    avg = 2;
                    d = 1;
                }
                int avg2 = 2 * (vec2[j] - time);

                if(avg > avg2) {
                    saved += ss;
                    time += d;
                    i++;
                } else {
                    saved += vec2[j] - time;
                    time++;
                    j++;
                }
            }

            while(i < vec.size() && vec[i] - 2*time > 0) {
                if(vec[i] - time * 2 <= 2) {
                    saved++;
                    time++;
                } else {
                    saved += vec[i] - time * 2 - 1;
                    time += 2;
                }
                i++;
            }

            while(j < vec2.size() && vec2[j] - time > 0) {
                saved += vec2[j] - time;
                j++;
                time++;
            }

            cout << n - saved << endl;

        } else {
            int j = 0;
            int time = 0;
            int saved = 0;
            while(j < vec2.size() && vec2[j] - time > 0) {
                saved += vec2[j] - time;
                j++;
                time++;
            }

            cout << n - saved << endl;
        }


    }

}