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
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#define ll long long
#define endl '\n'
using namespace std;

ll t, n;

void solve();

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> t;
    for(ll i = 0; i < t; i++)
        solve();
}

void solve()
{
    ll ilemiast = 0, len = 0, iledni = 0, i = 0;
    vector<bool> ar;
    priority_queue<ll> seg1, seg2;
    
    cin >> n;
    for(ll i = 0; i < n; i++)
    {
        char a;
        cin >> a;
        ar.push_back(a - '0');
    }
    ////////////////////////////////
    bool jeden = false;
    for(ll i = 0; i < n; i++)
        if(ar[i]) jeden = true;
    if(!jeden)
    {
        cout << 0 << endl;
        return;
    }
    /////////////////////////////////
    if(!ar[0])
    {
        for(i = 0; i < ar.size(); i++)
        {
            if(ar[i]) break;
            len++;
        }
        seg1.push(len);
        len = 0;
    }
    for(; i < n; i++)
    {
        if(ar[i])
        {
            if(len)
                seg2.push(len);
            len = 0;
        }
        else
            len++;
    }
    if(!ar[n-1] and len)
        seg1.push(len);

    while(!seg1.empty() or !seg2.empty())
    {
        ll ile1 = (seg1.size() ? seg1.top() - iledni : INT64_MIN);
        ll ile2 = (seg2.size() ? seg2.top() - iledni*2 : INT64_MIN);
        //cout << iledni << ' ' ;

        if(ile1 <= 0 and ile2 <= 0)
            break;

        if(ile1 + 2 >= ile2 and ile1 > 0)
        {
            seg1.pop();
            ilemiast += ile1;
            iledni++;
        }
        else
        {
            seg2.pop();
            if(ile2 > 2)
            {
                ilemiast += ile2 - 1;
                iledni += 2;
            }
            else
            {
                ilemiast++;
                iledni++;
            }
        }
    }

    cout << ar.size() - ilemiast << endl;
}