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
// Daniel Grzegorzewski
// while (clock()<=69*CLOCKS_PER_SEC)
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
// #pragma GCC optimize("Ofast")
// #pragma GCC target("avx,avx2,fma")

#define MP make_pair
#define PB push_back
#define ST first
#define ND second

using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

//X.find_by_order(k); - zwraca iterator na k-ty element (numeracja od zerowego)
//X.order_of_key(k); - zwraca liczbę elementów ostro mniejszych niż k

typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<PII> VII;
typedef long long LL;

void init_ios() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
}

auto random_address = [] { char *p = new char; delete p; return uint64_t(p); };
 
const uint64_t SEED = chrono::steady_clock::now().time_since_epoch().count() * (random_address() | 1);
mt19937_64 rng(SEED);

const int N = (int)1e5 + 3;

int t, n;
string s;

int main() {
  init_ios();
  cin >> t;
  while (t--) {
    cin >> n >> s;
    VI v[2];
    int lst = -1, res = 0;
    for (int i = 0; i < n; ++i) {
      if (s[i] == '0')
        continue;
      int len = i-lst-1;
      if (len == 0) {
        lst = i;
        continue;
      }
      if (lst == -1)
        v[0].PB(len);
      else
        v[1].PB(len);
      lst = i;
    }
    if (lst < n-1)
      v[0].PB(n-lst-1);
    sort(v[1].begin(), v[1].end());
    int si = (int)v[0].size();
    for (int msk = 0; msk < (1<<si); ++msk) {
      int tmp = 0, cnt = 0;
      for (int j = 0; j < si; ++j) {
        if (msk&(1<<j))
          tmp += v[0][j]-cnt++;
      }
      res = max(res, tmp);
      for (int i = 0; i < (int)v[1].size(); ++i) {
        int wie = v[1][v[1].size()-1-i]-4*i-2*cnt;
        if (wie <= 0)
          break;
        tmp += max(1, wie-1);
        res = max(res, tmp);
      }
    }
    cout<<n-res<<"\n";
  }
}