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
#include <iostream>

using namespace std;

int zera(int miasto[],int m){

    int z=0;
    int zm=0;
    int in=-1;
    int inm=-1;

    for(int i=0;i<m;i++){
        if(miasto[i]==0&&in==-1){
            z++;
            in=i;
        }else if(miasto[i]==0){
            z++;
        }else{
            if(zm<=z){
                zm=z;
                inm=in;

            }
             z=0;
            in=-1;

        }
    }
    if(zm<=z){
                zm=z;
                inm=in;

            }

    return inm;

}

void pandemia(int miasta[],int m){

    int i=0;
    if(miasta[i]==1){
        if(miasta[i+1]==0){
            miasta[i+1]=1;
            i+=2;
        }
    }

    for(int i=1;i<m;i++){
        if(miasta[i]==1){

            if(miasta[i-1]==0)miasta[i-1]=1;
            if(miasta[i+1]==0){
                miasta[i+1]=1;
                i+=1;
            }
        }

    }

}

int zliczanie(int miasta[],int m){

    int licznik=0;
    for(int i=0;i<m;i++){
        if(miasta[i]==1)licznik++;

    }


    return licznik;
}

int main()
{

   int t;
   cin>>t;

   int m;
   string miasta;

   int *miasta_tab;

   for(int k=0;k<t;k++){
    cin>>m;
    cin>>miasta;
    miasta_tab = new int[m];
    for(int i=0;i<m;i++){
        miasta_tab[i]=(int)miasta[i]-48;
    }

    int q;

    do{
        q=zera(miasta_tab,m);

        if(q==-1)break;
        for(int i=q;i<m;i++){
                if(miasta_tab[i]==0)miasta_tab[i]=2;
                else if(miasta_tab[i]==1&&q!=0){
                        miasta_tab[i-1]=1;
                        break;
                }
        }

        pandemia(miasta_tab,m);

    }while(q!=-1);


    cout<<zliczanie(miasta_tab,m)<<endl;
    delete [] miasta_tab;
   }

    return 0;
}