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
#include <bits/stdc++.h>


using namespace std;
#define LL long long

#define MAXN 100010
char buf[MAXN+10];

#define DBG(X) 

vector<int> parse(int n, char* buf)
{
    vector<int> intervals;
    int currentLen = 0;
    if (buf[0]=='1') intervals.push_back(0);
    for (int i=0; i < n; i++)
    {
        if (buf[i]=='1')
        {
            if (currentLen > 0) 
            {
                intervals.emplace_back(currentLen);
                currentLen = 0;
            }
        }
        else
        {
            ++currentLen;
        }
    }
    if (currentLen>0) intervals.emplace_back(currentLen);
    if (buf[n-1]=='1') intervals.push_back(0);
    return intervals;
}

void printVec(string name, const vector<int> &v)
{
    printf("%s", name.c_str());
    for (auto x : v)
    {
        printf("%d ", x);
    }
    printf("\n");
}

int solveInv(const vector<int> &intervals)
{
    DBG(printVec("intervals ", intervals));
    if (intervals.size() == 1)
    {
        return intervals[0];
    }
    vector<int> Hv{intervals[0], intervals[intervals.size()-1]};
    vector<int> Ov;
    for (int i=1; i < intervals.size()-1; i++)
    {
        Ov.emplace_back(intervals[i]);
    }
    sort(Hv.begin(), Hv.end()); reverse(Hv.begin(), Hv.end());
    sort(Ov.begin(), Ov.end()); reverse(Ov.begin(), Ov.end());
    DBG(printVec("Ov: ", Ov));
    DBG(printVec("Hv: ", Hv));

    deque<int> Q0{deque<int>(Ov.begin(), Ov.end())};
    deque<pair<int, int> > Q1;
    for (int i=0; i < Hv.size(); i++)
    {
        Q1.push_back(make_pair(Hv[i],0));
    }

    int daysCount = 0;
    int res = 0;
    while (true)
    {
        DBG(printf("Day %d\n", daysCount));
        int L0=0, L1=0;

        if (!Q0.empty())
        {
            L0 = Q0.front() - 2 * daysCount;
        }
        if (!Q1.empty())
        {
            L1 = Q1.front().first - daysCount;
            L1 = max(L1, Q1.front().second);
        }

        if (L1 <= 0 && L0 <= 0) break;
        DBG(printf("found L0=%d, L1=%d\n", L0, L1));
        if (L1 && L1+2 >= L0)
        {
            Q1.pop_front();
            DBG(printf("Saved %d cities\n", L1));
            res += L1;
        }
        else if (L0>0)
        {
            Q0.pop_front();
            Q1.push_front(make_pair(L0+daysCount,1));
            DBG(printf("Add %d to Q[1]\n", L0+daysCount));
        }
        ++daysCount;
    }
    return res;
}

int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        int n;

        scanf("%d", &n);
        scanf("%s", buf);
        vector<int> v = parse(n, buf);
        printf("%d\n", n-solveInv(v));
    }
}