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

using namespace std;

int goo (const deque<int> & V, int i) {
  int res = 0;
  for (auto v : V) {
    if (v-2*i <=0) break;
    if (v-2*i <=2) {
      res+=1;
      i+=1;
    } else {
      res+=v-2*i-1;
      i+=2;
    }
  }

  return res;
}


int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int t; cin >> t;
  while (t--) {
    int n; cin >> n;
    string S; cin >> S;
    S = '1' + S + '1';
    deque<int> V;
    for (int i=S.find('1', 0), j; (j=S.find('1', i+1))!=string::npos; i=j)
      V.push_back(j-i-1);
    int a = V.front(); V.pop_front();
    if (V.empty()) {
      cout << n-a << '\n';
      continue;
    }
    int b = V.back(); V.pop_back();
    sort(V.begin(), V.end(), greater<int>{});
    cout << n- max({goo(V, 0), max(a, b) + goo(V, 1), a+b-1+goo(V, 2)}) << '\n';
  }
  return 0;
}