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
#include <iostream>
#include <utility>
#include <algorithm>
using namespace std;
int n, base = 1048576, push1[2097152], push2[2097152], tabdl[1048577], t;
pair<int, int> t1[2097152], t2[2097152];
char c;

void add(int i, int ile, pair<int, int> t[], int push[]){
        t[i].first += ile;
        t[i].first = max(t[i].first, 0);
        push[i] += ile;
}

void pushFurther(int i, pair<int, int> t[], int push[]){
        add(i<<1, push[i], t, push);
        add((i<<1)+1, push[i], t, push);
        push[i] = 0;
}

void insert(int i, int pocz, int kon, int x, int y, int ile, pair<int, int> t[], int push[]){
        if(x <= pocz && kon <= y){
                add(i, ile, t, push);
                return;
        }

        pushFurther(i, t, push);

        int sr = (pocz+kon)>>1;

        if(x <= sr) insert(i<<1, pocz, sr, x, y, ile, t, push);
        if(sr < y) insert((i<<1)+1, sr+1, kon, x, y, ile, t, push);

        if(t[i<<1].first == t[(i<<1)+1].first){
                if(tabdl[t[i<<1].second] % 2 == 0 && tabdl[t[(i<<1)+1].second] % 2 != 0){
                        t[i] = t[i<<1];
                }
                else t[i] = t[(i<<1)+1];
        }
        else t[i] = max(t[i<<1], t[(i<<1)+1]);
}

pair<int, int> query(int i, int pocz, int kon, int x, int y, pair<int, int> t[], int push[]){
        if(x <= pocz && kon <= y){
                return t[i];
        }

        pushFurther(i, t, push);

        int sr = (pocz+kon)>>1;
        pair<int, int> wynik = {0, 0}, one = {0, 0},
                                       two = {0, 0};

        if(x <= sr) one = query(i<<1, pocz, sr, x, y, t, push);
        if(sr < y) two = query((i<<1)+1, sr+1, kon, x, y, t, push);

        if(t[i<<1].first == t[(i<<1)+1].first){
                if(tabdl[t[i<<1].second] % 2 == 0 && tabdl[t[(i<<1)+1].second] % 2 != 0){
                        t[i] = t[i<<1];
                }
                else t[i] = t[(i<<1)+1];
        }
        else t[i] = max(t[i<<1], t[(i<<1)+1]);

        if(one.first == two.first){
                if(tabdl[one.second] % 2 == 0 && tabdl[two.second] % 2 != 0){
                        wynik = one;
                }
                else wynik = two;
        }
        else wynik = max(one, two);

        return wynik;
}

int main()
{
    for(int i = base; i < base<<1; ++i) t1[i].second = t2[i].second = i-base+1;
    for(int i = base-1; i >= 1; --i) t1[i].second = t2[i].second = t1[(i<<1)+1].second;
    scanf("%d", &t);
    int index = 0, beg = 0;
    for(int z = 0; z < t; ++z){
            scanf("%d\n", &n);

            if(index + n > 1000000){
                    for(int i = base; i < base<<1; ++i){
                            t1[i].second = t2[i].second = i-base+1;
                            t1[i].first = t2[i].first = 0;
                            push1[i] = push2[i] = 0;
                            tabdl[i] = 0;
                    }
                    for(int i = base-1; i >= 1; --i){
                            t1[i].second = t2[i].second = t1[(i<<1)+1].second;
                            t1[i].first = t2[i].first = 0;
                            push1[i] = push2[i] = 0;
                    }
                    index = 0, beg = 0;
            }

            int wynik = n, last = 0;
            bool pocz = 1;
            beg = index + 1;
            for(int i = 1; i <= n; ++i){
                    scanf("%c", &c);

                    if(c == '1'){
                            ++index;
                            int dl = i-last-1;
                            last = i;
                            tabdl[index] = dl;
                            if(pocz || dl == 1){
                                    insert(1, 1, base, index, index, dl, t1, push1);//1
                                    pocz = 0;
                            }
                            else{
                                    insert(1, 1, base, index, index, (dl&1)==1 ? (dl>>1)+1 : dl>>1, t2, push2);//2
                            }
                    }

            }
            ++index;
            insert(1, 1, base, index, index, n-last, t1, push1); // n+1-last-1
            tabdl[index] = n-last;

            while(true){
                    pair<int, int> tmp1 = query(1, 1, base, beg, index, t1, push1),
                                   tmp2 = query(1, 1, base, beg, index, t2, push2);

                    if(!tmp1.first && !tmp2.first) break;
                    if(tmp1.first >= tmp2.first){
                            pair<int, int> t = query(1, 1, base, tmp1.second, tmp1.second, t1, push1);
                            insert(1, 1, base, tmp1.second, tmp1.second, -t.first, t1, push1);
                            wynik -= t.first;
                    }

                    else{
                            pair<int, int> t = query(1, 1, base, tmp2.second, tmp2.second, t2, push2);
                            insert(1, 1, base, tmp2.second, tmp2.second, -t.first, t2, push2);
                            if(t.first != 1){
                                    insert(1, 1, base, tmp2.second, tmp2.second, ((t.first-1)<<1) + (tabdl[tmp2.second]%2==0 ? 1 : 0), t1, push1);
                            }
                            --wynik;
                    }

                    insert(1, 1, base, beg, index, -1, t1, push1);
                    insert(1, 1, base, beg, index, -1, t2, push2);

            }

            printf("%d\n", wynik);
    }
    return 0;
}