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

struct sub
{
    int i;
    int j;
    int type;
};

bool operator<(sub a, sub b)
{
    return a.j-a.i<b.j-b.i;
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        string s;
        cin>>s;
        vector<int> v(n);
        for(int i=0; i<n; ++i)
            v[i]=s[i]-'0';
        int result=0;
        int counter=0;
        for(int i=0; i<n; ++i)
            if(v[i]==1)
                ++result;
        if(n-result<=1)
            cout<<result<<endl;
        if(n-result==2)
        {
            if((v[0]==0&&v[1]==0)||(v[n-2]==0&&v[n-1]==0))
                cout<<result<<endl;
            else
                cout<<result+1<<endl;
        }
        if(n-result>2)
        {
            priority_queue<sub> q;
            int state=1;
            int beg=-1;
            for(int p=0; p<n; ++p)
            {
                if(state==1)
                    if(v[p]==0)
                    {
                        state=0;
                        beg=p;
                    }
                if(state==0)
                    if(v[p]==1)
                    {
                        state=1;
                        if(beg==0)
                            q.push({beg,p-1,1});
                        else
                            q.push({beg,p-1,0});
                    }
            }
            if(state==0)
                q.push({beg,n-1,1});

            while(!q.empty())
            {
                sub current=q.top();
                q.pop();
                if(current.type==1)
                {
                    result+=min(counter,current.j-current.i+1);
                    if(current.j==n-1)
                        current.i+=counter;
                    else
                        current.j-=counter;
                    if(current.i<=current.j)
                        ++counter;
                }
                else
                {
                    result+=min(2*counter,current.j-current.i+1);
                    current.i+=counter;
                    current.j-=counter;                    
                    if(current.i==current.j)
                        ++counter;
                    if(current.i==current.j-1)
                    {
                        ++counter;
                        ++result;
                    }
                    if(current.i<current.j-1)
                    {
                        counter+=2;
                        ++result;
                    }
                }
            }
            cout<<result<<endl;
        }
    }
    return 0;
}