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
#include <iostream>

using namespace std;

unsigned long tab[100001], nr_left, nr_right;
void print_tab() {
    for (int i = 0; i < 101; i++) cout << i << "/" << tab[i] << " ";
    cout << endl << "left=" << nr_left << " right=" << nr_right << endl;
}

void przypadek_testowy() {
    unsigned long n, i = 0, j, wolne = 0, rund = 0;
    char ch;
    cin >> n;
    do { cin >> ch; i++; } while (ch == '0' && i < n);
    if (ch == '0') { cout << "0" << endl; return; }
    nr_left = i - 1; nr_right = 0;
    for (j = 1; j < n; j++) tab[j] = 0;
    do {
        do { cin >> ch; i++; } while (ch == '1' && i < n);
        if (ch == '0') {
            j = 1;
            while (ch == '0' && i < n) { cin >> ch; i++; j++; }
            if (ch == '1') {
                tab[--j]++;
                if (i == n) break;
            }
            else { nr_right = j; break; }
        }
        else break;
    } while (1);
    j = n;
//    print_tab();
    do {
        while (tab[j] == 0 && j > rund + rund) j--;
        if (j > rund + rund + 2) {
            if (nr_left >= j - rund - 1) { wolne += nr_left - rund++; nr_left = 0 ; }
            else if (nr_right >= j - rund - 1) { wolne += nr_right - rund++; nr_right = 0; }
            else if (nr_left + nr_right > j  && j - 4 * rund == 1) {
                wolne += nr_right - rund + nr_left - rund - 1; rund += 2; nr_left = nr_right = 0; 
            }
            else {
                wolne += j - 1 - rund - rund; rund += 2;
                tab[j]--;
            }
/*        } else if (j == rund + rund + 2) {
            if (nr_left > rund) { wolne += nr_left - rund++; nr_left = 0 ; }
            if (nr_right > rund) { wolne += nr_right - rund++; nr_right = 0; }
            if (j == rund + rund + 2) {
                wolne += j - 1 - rund - rund; rund += 2;
                tab[j]--;
            }
*/        }
        else if (j > rund + rund) { //else if (j == rund + rund + 1) {
            if (nr_left > rund) { wolne += nr_left - rund++; nr_left = 0 ; }
            if (nr_right > rund) { wolne += nr_right - rund++; nr_right = 0; }
            if (j > rund + rund) { //if (j == rund + rund + 1) {
                wolne++; rund++; //wolne += j - rund - rund; rund++;
                tab[j]--;
            }
        }
        else break;
    } while (1);
    if (nr_left > rund) wolne += nr_left - rund++;
    if (nr_right > rund) wolne += nr_right - rund;
    cout << n - wolne << endl;
}

int main()
{
    unsigned long t;
    cin >> t;
    while (t-- > 0)
        przypadek_testowy();

    return 0;
}