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
//Autor:Szymon Nowak
#include <iostream>

using namespace std;

void quicksort(int* tablica, int lewy, int prawy,int* d)
{
    int v=tablica[(lewy+prawy)/2];
    int i,j,x;
    i=lewy;
    j=prawy;
    do
    {
        while (tablica[i]<v) i++;
        while (tablica[j]>v) j--;
        if (i<=j)
        {
            swap(tablica[i],tablica[j]);
            swap(d[i],d[j]);
            i++;
            j--;
        }
    }
    while (i<=j);
    if (j>lewy) quicksort(tablica,lewy, j,d);
    if (i<prawy) quicksort(tablica, i, prawy,d);
}

void rozprzestrzenianie(int *strony_zarazania,int *ile_zer,int y)
{
    for(int i=0;i<=y;i++)
    {
        if(ile_zer[i]<strony_zarazania[i]) {strony_zarazania[i]=0; ile_zer[i]=0;}
        ile_zer[i]-=strony_zarazania[i];
    }
}

const int MAX=1e5+10;
int ile_zer[MAX];
int strony_zarazania[MAX];
char tablica[MAX];

int main()
{
    int t;
    cin>>t;

    for(int i=1;i<=t;i++)
    {
        int n;
        cin>>n;

        for(int j=0;j<n;j++)
        {
           cin>>tablica[j];
           ile_zer[j]=0;
        }

        int y=-1;
        int x=0;

        while(x<n)
        {
        if(tablica[x]=='0')
            {
                y++;
                while(tablica[x]=='0' && x<n)
                {
                    ile_zer[y]+=1;
                    x++;
                }
            }
            x++;
        }
    for(int j=0;j<n;j++) strony_zarazania[j]=2;

    if(tablica[0]!='1') strony_zarazania[0]=1;
    if(tablica[n-1]!='1') strony_zarazania[y]=1;

    int z=y;
    int suma_zarazaczy;
    for(int i=0;i<=y;i++) suma_zarazaczy+=strony_zarazania[i];

    while(suma_zarazaczy!=0)
    {
        z=y;
        quicksort(ile_zer,0,y,strony_zarazania);
        while(strony_zarazania[z]==0 && z>=0) z--;

            strony_zarazania[z]-=1;
            rozprzestrzenianie(strony_zarazania,ile_zer,y);


        suma_zarazaczy=0;
        for(int i=0;i<=y;i++) suma_zarazaczy+=strony_zarazania[i];
    }

    int suma=0;
    for(int i=0;i<=y;i++) suma+=ile_zer[i];
    cout<<n-suma<<"\n";

    }
    return 0;
}