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

void solve(){
  int n;
  string s;
  cin >> n >> s;
  priority_queue<int> q;

  int lewy = 0, prawy = 0;
  {
    int i = 0;
    while (i < n && s[i] != '1') i++;
    lewy = i;
    for(int combo = 0;i < n;i++){
      if (s[i] == '1') {
        if (combo > 0)
          q.emplace(combo);
        combo = 0;
      }
      combo += s[i] == '0';
    }
    while(prawy < n && s[n - 1 - prawy] == '0') prawy++;
    q.emplace(0);
    q.emplace(0);
    q.emplace(0);
  }
  if (lewy == n){
    cout << 0 << '\n';
    return;
  }
  
  int res = 0;
  int time = 0;
  while(!q.empty()){
    int x = q.top() - 2 * time;

    /* printf("Lewo: %d, Srodek: %d, Prawo: %d\n", lewy, x, prawy); */

    if (lewy > 0 && lewy >= prawy && lewy >= x - 1 - (x > 1)) {
      res += lewy;
      lewy = 0;
      prawy--;
      time++;
      continue;
    }

    if(prawy > 0 && prawy >= lewy && prawy >= x - (x > 1)){
      res += prawy;
      prawy = 0;
      lewy--;
      time++;
      continue;
    }

    q.pop();

    if(x == 1){
      res += 1;
      time++;
      lewy--;
      prawy--;
      continue;
    }

    x -= 1;
    if (x <= 0) continue;
    res += x;
    lewy -= 2;
    prawy -= 2;
    time += 2;
  }
  cout << n - res << '\n';
}

int main(){
  ios_base::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  int t = 1;
  for(cin >> t;t;--t)
    solve();
}