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
#include <cstdio>
#include <vector>
#include <set>
#include <tuple>
#include <algorithm>
#include <map>
#define MAX_N 100010
#define NO_ID 21372137
using namespace std;

char s[MAX_N];

int test() {
    int n;
    vector<int> ones, twos;


    scanf("%d", &n);
    scanf("%s", s);

    int len = 0;
    int zar = 0;
    bool anyVirus = false;

    for (int i = 0; i < n; i++) {
        if (s[i] == '1') {
            zar++;
            if (anyVirus) {
                if (len > 0) {
                    twos.push_back(len);
                }
                len = 0;
            } else {
                if (len > 0) {
                    ones.push_back(len);
                }
                len = 0;
            }
            anyVirus = true;
        } else {
            len++;
        }
    }
    if (!anyVirus) {
        return 0;
    }
    if (len > 0) {
        ones.push_back(len);
    }
    //printf("ones: ");
    //for (int i = 0; i < ones.size(); i++) printf("%d, ", ones[i]);
    //printf("\ntwos: ");
    //for (int i = 0; i < twos.size(); i++) printf("%d, ", twos[i]);
    //printf("\n");

    int id = 0;
    set<pair<int, pair<int, int> > > all;
    map<int, int> sizes;

    sort(ones.begin(), ones.end());
    sort(twos.begin(), twos.end());

    for (auto i : ones) {
        all.emplace(i, make_pair(NO_ID, id));
        sizes[id] = i;
        id++;

    }
    for (auto i : twos) {
        int id1 = id;
        int id2 = id + 1;
        int size1 = i / 2;
        int size2 = (i + 1) / 2;
        sizes[id1] = size1;
        sizes[id2] = size2;

        all.emplace(size1, make_pair(id2, id1));
        all.emplace(size2, make_pair(id1, id2));
        id += 2;
    }

    int day = 0;
    while (!all.empty()) {
        //printf("\n\nDAY %d, zar: %d\n",day, zar);
        //for (auto i : all) {
        //    printf (" - %d (%d -> %d)\n", i.first, i.second.first, i.second.second);
        //}

        pair<int, pair<int, int>> prio = *(--all.end());
        //printf("SELECTED: ");
        //printf (" - %d (%d -> %d)\n", prio.first, prio.second.first, prio.second.second);

        zar += day;
        int left = prio.first - day - 1;
        int comp_id = prio.second.first;
        int my_id = prio.second.second;

        all.erase(prio);

        if (comp_id != NO_ID) {
            pair<int, pair<int, int>> comp = make_pair(sizes[comp_id], make_pair(my_id, comp_id));
            all.erase(comp);

            pair<int, pair<int, int>> new_comp = make_pair(sizes[comp_id] + left, make_pair(NO_ID, comp_id));
            all.insert(new_comp);
        }

        day++;
        while (!all.empty() && (*all.begin()).first <= day) {
            pair<int, pair<int, int> > xd = *all.begin();
            zar += xd.first;
            all.erase(xd);

            int comp_id = xd.second.first;
            int my_id = xd.second.second;

            if (comp_id != NO_ID) {
                pair<int, pair<int, int>> comp = make_pair(sizes[comp_id], make_pair(my_id, comp_id));
                all.erase(comp);

                pair<int, pair<int, int>> new_comp = make_pair(sizes[comp_id], make_pair(NO_ID, comp_id));
                all.insert(new_comp);
            }
        }
    }

    return zar;
    //1001000010

}

int main() {
    int t;
    scanf("%d", &t);
    for (int i = 0; i < t; i++) printf("%d\n", test());
}