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
137
138
139
140
141
142
143
144
145
146
147
148
149
150
#include <iostream>

using namespace std;

void quicksort(int *tablica, int lewy, int prawy)
{
    int t = tablica[(lewy + prawy)/2];
    int i, l = lewy, p = prawy;
    do
    {
        while(tablica[l] > t)
        {
            l++;
        }
        while(tablica[p] < t)
        {
            p--;
        }

        if(l <= p)
        {
            i = tablica[l];
            tablica[l] = tablica[p];
            tablica[p] = i;
            l++;
            p--;
        }
    }
    while(l <= p);

    if(p > lewy)
    {
        quicksort(tablica, lewy, p);
    }
    if(l < prawy)
    {
        quicksort(tablica, l , prawy);
    }
}

int main()
{
    int t, n, i, j, l, p, z, d, a;
    int left, right, wynik;
    cin >> t;
    for(i = 0; i < t; i++)
    {
        cin >> n;
        p = n-1;
        l = 0;
        string miasta;
        cin >> miasta;
        left = 0; right = 0;

        if(miasta[l] == '0')
        {
            while(l < p)
            {
                l++;
                if(miasta[l] == '1')
                {
                    left = l;
                    break;
                }
            }
        }
        if(miasta[p] == '0')
        {
            while(p >= 0)
            {
                p--;
                if(miasta[p] == '1')
                {
                    right = n - 1 - p;
                    break;
                }
            }
        }
        if(p < l)
        {
            cout << 0 << endl;
        }
        else
        {
            int *odleglosc;
            odleglosc = new int[p+1];

            z = l;
            d = 0;

            for(j = l + 1; j <= p; j++)
            {
                if(miasta[j] == '1')
                {
                    odleglosc[d] = j- z - 1;
                    d++;
                    z = j;

                }
            }

            quicksort(odleglosc, 0, d-1);

            a = 0;
            wynik = 0;
            while(odleglosc[a] > 0 || left > 0 || right > 0)
            {
                if(odleglosc[a] > left && odleglosc[a] > right)
                {
                    wynik += odleglosc[a] - 1;
                    odleglosc[a] = 0;
                    a++;
                    for(j = a; j <= d; j++)
                    {
                        odleglosc[j] -= 4;
                    }
                    left-=2;
                    right-=2;
                }
                else if(left >= odleglosc[a] && left >= right)
                {
                    wynik += left;
                    left = 0;
                    right-=1;
                    for(j = a; j <= d; j++)
                    {
                        odleglosc[j] -=2;
                    }
                }
                else
                {
                    wynik+=right;
                    right = 0;
                    for(j = a; j <= d; j++)
                    {
                        odleglosc[a]-=2;
                    }
                    left-=1;

                }
            }
            cout << n - wynik << endl;

            delete [] odleglosc;
        }


    }
    return 0;
}