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
#include <cstdio>
#include <algorithm>
#include <functional>

using namespace std;

#define MAXN 200000
char datadata[MAXN];
typedef struct interval {
  int lgt;
  int ends;
} inter;
inter inters[MAXN];

inline int val(const inter &A) {
  return A.lgt * (3 - A.ends);
}

bool operator< (const inter &A, const inter &B) {
  return val(A) > val(B);
}


int main() {
  int T;
  scanf("%d", &T);
  for (int ttt = 0; ttt < T; ++ttt) {
    int N;
    scanf("%d\n", &N);
    scanf("%s\n", datadata);     
    int cur_inter = 0;
    int n_inters = 1;
    inters[0].lgt = inters[0].ends = 0;
    for (int i = 0; i < N; ++i) {
      if (cur_inter >= 0) {
        if (datadata[i] == '0') {
          inters[cur_inter].lgt += 1;
        } else {
          inters[cur_inter].ends += 1;
          cur_inter = -1;
        } 
      } else {
        if (datadata[i] == '0') { 
          cur_inter = n_inters;
          inters[cur_inter].lgt = 1;
          inters[cur_inter].ends = 1;
          n_inters += 1;
        }
      } 
    }
    sort(&inters[0], &inters[n_inters]);

    int cround = 0;
    int cscore = 0;
    for (int i = 0; i < n_inters; ++i) {
      int cval = inters[i].lgt - inters[i].ends * cround;
      if (inters[i].ends == 2 && cval > 1) cval -= 1;
      if (cval > 0) cscore += cval;
      cround += inters[i].ends;
    }
    printf("%d\n", N - cscore);
  }
  return 0;
}