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

using namespace std;

int n;

void solve() {
  cin >> n;
  
  string s;
  cin >> s;
  

  int l = 0;
  vector<int> v;
  for (int i = 0; i < n; ++i) {
    if (s[i] == '1') {
      if (i != l)
        v.push_back(i - l);
      l = i + 1;
    }
  }
  int left = 0, right = 0;
  if (s.back() == '0') {
    right = n - l;
  }
  if (!v.empty() && s[0] == '0') {
    left = v[0];
    v.erase(v.begin());
  }


  sort(v.begin(), v.end(), greater<int>());
  // cout << "V: ";
  // for (int &i : v)
  //   cout << i << ' ';
  // cout << '\n';

  int sum = 0, time = 0;
  for (int i = 0; i < v.size();) {
    if (left - time == 3 && right - time == 3 && v[i] - time == 5) {
      cout << n - sum - 6 << '\n';
      return;
    }
    if ((left > time || right > time) && (left >= v[i] - 1 || right >= v[i] - 1)) {
      if (left > right) {
        sum += left - time;
        time += 2;
        ++right;
        left = 0;
      } else {
        sum += right - time;
        time += 2;
        ++left;
        right = 0;
      }
      // cout << "SUM IS NOW: " << sum << '\n';
      // cout << "TIME IS NOW: " << time << '\n';
      continue;
    }
    if (v[i] <= time)
      break;
    if (v[i] == time + 1) {
      ++sum;
      ++time;
      // cout << "SUM IS NOW: " << sum << '\n';
      // cout << "TIME IS NOW: " << time << '\n';
      break;
    }
    sum += v[i] - time - 1;
    time += 4;
    left += 2;
    right += 2;
    // cout << "SUM IS NOW: " << sum << '\n';
    // cout << "TIME IS NOW: " << time << '\n';
    ++i;
  }
  if (left > time) {
    sum += left - time++;
    // cout << "SUM IS NOW: " << sum << '\n';
  }
  if (right > time) {
    sum += right - time;
    // cout << "SUM IS NOW: " << sum << '\n';
  }
  cout << n - sum << '\n';
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int z; cin >> z;
  while (z--)
    solve();
}