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

#define st first
#define nd second
#define pb(x) push_back(x)
#define pp(x) pop_back(x)
#define mp(a, b) make_pair(a, b)
#define all(x) (x).begin(), (x).end()
#define rev(x) reverse(all(x))
#define sor(x) sort(all(x))
#define sz(x) (int)(x).size()
#define rsz(x) resize(x)

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<pii > vii;
typedef vector<ll> vl;
typedef vector<pll> vll;
typedef string str;
#define BOOST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
const int MN=1e5+7;
bitset <MN> dane;
void barr()
{
    cerr<<"good\n";
}
bool cmp(pair<int,bool> a, pair<int, bool> b)
{
    if(a.st>b.st) return 1;
    return 0;
}
int main()
{
    BOOST
    int t,n;
    cin>>t;
    vector < pair<int, bool> >tab;
    bool aktual, poprz,pierwszy, fi, la;
    vector <int> zmiana; char znak;
    int poprpoz, licz, ind;
    int x, wyn;
    for(int i=0; i<t; i++)
    {
        cin>>n;
       //cin>>poprz;
       tab.clear();
        for(int i=0 ;i<n; i++)
            {
                cin>>znak;
                dane[i]=(bool)(znak=='1');
            }
        licz=0;
        dane[n]=(!dane[n-1]);
        while(licz<n)
        {
            if(dane[licz]==0)
            {
                ind=1;
                while(licz<n-1 and dane[licz+1]==0)
                {
                    licz++; ind++;
                }
                tab.pb(mp(ind, 0));
                licz++;
            }
            else
            {
                while(licz<n-1 and dane[licz+1]==1)
                {
                    licz++;
                }
                licz++;
            }
        }
    /*
        for(int i=0; i<tab.size(); i++)
            cout<<tab[i].st<<' ';
        cout<<"\n";
    */
        if(tab.size()==1 and dane[0]==0 and dane[n-1]==0)
        {
            cout<<0<<"\n"; continue;
        }
        if(tab.size()==0) {cout<<n<<"\n"; continue; }

        if(dane[0]==0) {tab[0].nd=1; tab[0].st*=2; }
        if(dane[n-1]==0) {tab[tab.size()-1].nd=1; tab[tab.size()-1].st*=2; }
        sort(tab.begin(), tab.end(), cmp);
    /*
        for(int i=0; i<tab.size(); i++)
        cout<<tab[i].st<<' ';
        cout<<"\n";
    */
        wyn=0; x=0;
        for(int i=0; i<tab.size(); i++)
        {
            if(tab[i].nd==0)
            {

               if(tab[i].st-2*x==1)
                wyn+=1;
               else wyn += max(0, tab[i].st - 2*x - 1);
                x+=2;
            }
            if(tab[i].nd==1)
            {
                wyn+=max(0, tab[i].st/2 - x);
                x++;
            }
        }
        wyn=n-wyn;
        cout<<wyn<<"\n";
    }
}