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
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
#include <iostream>
#include <vector>

using namespace std;

struct Section{
    int begin;
    int end;
    int len;
    int score;
};

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

    int t, n;
    bool is_section;
    int section_l, section_r;
    int len;
    int result;
    char c;

    int tab[100002];
    vector<Section> sections;

    cin >> t;

    for (int j = 0; j < t; ++j) {
        cin >> n;
        is_section = false;
        result = 0;
        sections.clear();
    
        for(int i = 0; i < 100002; ++i) {
            tab[i] = 2;
        }

        for (int i = 1; i <= n; ++i) {
            cin >> c;
            tab[i] = c - '0';
        }
        
        for (int i = 1; i <= n + 1; ++i) {
            if (tab[i] == 0) {
                if (!is_section) {
                    is_section = true;
                    section_l = i;
                }
            } else {
                if (is_section) {
                    is_section = false;
                    section_r = i - 1;
                    Section s;
                    s.begin = section_l;
                    s.end = section_r;
                    s.len = section_r - section_l + 1;
                    s.score = 0;
                    if (tab[section_l - 1] == 1) {
                        ++s.score;
                    }
                    if (tab[section_r + 1] == 1) {
                        ++s.score;
                    }
                    //cerr << '[' << s.begin << ' ' << s.end << ' ' << s.len << ' ' << s.score << ']' << endl;
                    if (s.score > 0) {
                        //cerr << '[' << s.begin << ' ' << s.end << ' ' << s.score << ']' << endl;
                        sections.push_back(s);
                    }
                }
            }

        }

        int day = 1;
        while (! sections.empty()) {
            //cerr << "DAY: " << day++ << endl;
            //DEBUG
            // for (int i = 0; i <= n+1; ++i) {
            //     //cerr << tab[i];
            // }
            //cerr << endl;
            //

            Section * vac = nullptr;
            // int high_score = 0;
            // int high_len = 0;
            //cerr << "SEARCH";
            for (auto it = sections.begin(); it != sections.end(); ++it) {
                //cerr << ".";
                if (vac == nullptr || it->len > vac->len) {
                    if (tab[it->begin] == 0) {
                        vac = &(*it);
                        //cerr << 'f';
                    }
                } else if (it->len == vac->len) {
                    if (tab[it->begin] == 0 && it->score < vac->score) {
                        vac = &(*it);
                        //cerr << 'f';
                    }
                }
            }
            
            //cerr << endl;

            if (vac == nullptr) {
                break; 
            }

            //cerr << "VAC";
            if (tab[vac->begin - 1] == 1) {
                //cerr << "x";
                tab[vac->begin] = 2;
                vac->begin = vac->begin + 1;
            } else if (tab[vac->end + 1] == 1) {
                //cerr << "o";
                tab[vac->end] = 2;
                vac->end = vac->end - 1;
            } else {
                //cerr << 'U' << endl;
                // 2 B ... E 2
                // unreachable
            }
            vac->len = vac->end - vac->begin + 1;
            vac->score = 0;
            if (tab[vac->begin] == 0 && tab[vac->end] == 0) {
                    
                if (tab[vac->begin - 1] == 1) {
                    vac->score += 1;
                }
                if (tab[vac->end + 1] == 1) {
                    vac->score += 1;
                }
                //cerr << '(' << it->begin << ' ' << it->end << ' ' << it->len << ' ' << it->score << ')' << endl;
            }
            //cerr << endl;

            // cerr << "BEFORE SPREAD" << endl;
            // for (int i = 0; i <= n+1; ++i) {
            //     cerr << tab[i];
            // }
            // cerr << endl;
            for (auto it = sections.begin(); it != sections.end(); ++it) {
                //cerr << '(' << it->begin << ' ' << it->end << ' ' << it->len << ' ' << it->score << ')' << endl;
                //cerr << "." << endl;
                int len_up = 0;
                if (tab[it->begin] == 0 && tab[it->begin - 1] == 1) {
                    tab[it->begin] = 1;
                    it->begin = it->begin + 1;
                    ++len_up;
                }
                if (tab[it->begin] == 0 && tab[it->end + 1] == 1) {
                    tab[it->end] = 1;
                    it->end = it->end - 1;
                    ++len_up;
                }
                it->len -= len_up;
                it->score = 0;
                if (tab[it->begin] == 0 && tab[it->end] == 0) {
                    
                    if (tab[it->begin - 1] == 1) {
                        it->score += 1;
                    }
                    if (tab[it->end + 1] == 1) {
                        it->score += 1;
                    }
                    //cerr << '(' << it->begin << ' ' << it->end << ' ' << it->len << ' ' << it->score << ')' << endl;
                }
                
            }
            // cerr << "AFTER SPREAD" << endl;
            // for (int i = 0; i <= n+1; ++i) {
            //     cerr << tab[i];
            // }
            // cerr << endl;

            for (int i = 0; i<sections.size(); ++i) {
                if (sections[i].score == 0) {
                    sections.erase(sections.begin() + i);
                }
            }

        }

        for (int i = 1; i <= n; ++i) {
            if (tab[i] == 1) {
                ++result;
            }
        }

        cout << result << '\n';

    }

    return 0;
}