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
#include<bits/stdc++.h>
using namespace std;
const int R=1e6+6;
#define fr first
#define sc second
using pii=pair<int,int>;
int tab[R];
vector<int>virus;
int main()
{
   ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
   int t;cin>>t;
   while(t--)
   {
      virus.clear();
      memset(tab,0,sizeof(tab));
      int n;cin>>n;
      string s;cin>>s;
      int p=-1,d=0;
      for(int j=0;j<s.size();j++)
      {
         if(s[j]=='1')virus.push_back(j);
      }
      if(virus.empty())
      {
         cout<<0<<"\n";
         continue;
      }
      if(virus.size()==1)
      {
         if(virus[0]==0||virus[0]==n-1)
         {
            cout<<1<<"\n";
         }
         else cout<<2<<"\n";
         continue;
      }
      int o=0,z=0;
      if(virus[0]!=0)
      {
         tab[virus[0]]+=1;
         //z+=virus[0];
         //o++;
      }
      for(int i=1;i<virus.size();i++)
      {
         int d=virus[i]-virus[i-1]-1;
         tab[d]+=2;
      }
      if(virus.back()!=n-1)
      {
         tab[n-1-virus.back()]+=1;
        //b=n-1-virus.back();
        //o++;
      }
      for(int j=n-1;j>0;j--)
      {
         if(!tab[j])continue;
         if(j-o<=0)break;
         if(j-1==n-1-virus.back()||j-1==virus.front())
         {
            j--;
            if(n-1-virus.back()==j&&virus.back()!=n-1&&j-o>0)
            {
               z+=j-o;
               o++;
               tab[j]--;
               virus[virus.size()-1]=-1;
            }
            if(virus.front()==j&&j-o>0)
            {
               tab[j]--;
               z+=j-o;
               o++;
               virus[0]=-1;
            }
            j++;
         }
         while(tab[j])
         {
            if(j-o<=0)break;
            else if(n-1-virus.back()==j&&virus.back()!=n-1)
            {
               z+=j-o;
               o++;
               tab[j]--;
               virus[virus.size()-1]=-1;
            }
            else if(virus.front()==j)
            {
               tab[j]--;
               z+=j-o;
               o++;
               virus[0]=-1;
            }
            else
            {
               if(j-2*o<1)break;
               else if(j-2*o==1)
               {
                  z++;
                  o++;
                  break;
               }
               z+=j-o*2-1;
               o+=2;
               tab[j]-=2;
            }
         }
      }
      cout<<n-z<<"\n";
   }
}