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

int pyt,n;
string s;
priority_queue<pair<int,pair<int,int> > > q;

int policz(int a, int b){
  int x = b-a+1;
  int wynik = x/2;
  if(x%2 == 1) wynik++;
  return wynik;
}

int policz_wynik(){
  if(q.empty()) return n;
  int ile = 0, wynik = 0;
  while(!q.empty()){
    int left = q.top().first, a = q.top().second.first, b = q.top().second.second;
    // cerr<<"teraz rozpatruje przedzial ("<<a<<","<<b<<")  ktoremu zostalo "<<left<<" ruchow"<<endl;
    q.pop();
    if((a == 0 && b < n-1)||(a > 0 && b == n-1)){
      if(b-a-ile+1 > 0){
        // cerr<<"to jest skrajny przedzial lewy lub prawy"<<endl;
        // cerr<<"dodaje do wyniku "<<b-a-ile+1<<endl;
        wynik+= b-a-ile+1, ile++;
        // cerr<<"ten przedzial wystarczy zaszczepic tylko raz"<<endl;
      }
    }
    else if(a > 0 && b < n-1){
      a+=ile, b-=ile;
      if(a <= b){
        // cerr<<"przesuwam poczatek w prawo o "<<ile<<" i koniec w lewo o "<<ile<<endl;
        // cerr<<"a = "<<a<<"   b = "<<b<<endl;
        if(b-a < 2){
          wynik++, ile++;
          // cerr<<"przedzial max 2-el ktory moge zaszczepic raz i nie ma wiecej elementow"<<endl;
          // cerr<<"dodaje do wyniku 1"<<endl;
        }
        else if(b-a >= 2){
          // cerr<<"ten przedzial trzeba zaszczepic 2 razy"<<endl;
          b--;
          // cerr<<"dodaje do wyniku "<<b-a+1<<endl;
          wynik+= b-a+1, ile+=2;
          // cerr<<"zaszczepilem w "<<a<<" i przesunalem koniec z "<<b+1<<" do "<<b<<endl;
        }
      }
    }
  }
  if(ile == 0) return 0;
  return n-wynik;
}

int main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin>>pyt;
  for(int i = 0; i < pyt; i++){
    cin>>n>>s;
    int j = 0;
    while(j < n){
      while(j < n && s[j] == '1') j++;
      int pocz = j;
      while(j < n && s[j] == '0') j++;
      int kon = j-1;
      if(pocz <= kon){
        int ruchy = policz(pocz,kon);
        q.push({ruchy,{pocz,kon}});
      }
    }
    cout<<policz_wynik()<<"\n";
  }
  // while(!q.empty()){
  //   int x = q.top().first, y = q.top().second.first, z = q.top().second.second;
  //   cout<<"("<<y<<","<<z<<") and "<<x<<" turns left"<<endl;
  //   q.pop();
  // }
  return 0;
}