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
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include <cstring>
#include <cstdio>
#include <map>
#include <algorithm>

const int max_n = 500011;
char input[max_n];
int a[max_n];
int b[max_n];
int n, an, bn;

int maxx(int a, int b) {
  return a > b ? a : b;
}

int minn(int a, int b) {
  return a < b ? a : b;
}

void gogo() {
  scanf(" %d ", &n);
  scanf(" %s ", &input);
  int current = 0;
  an = bn = 0;
  for (int i = 0; i < n; ++i) {
    if (input[i] == '1') {
      if (current > 0) {
        if (current == i) {
          b[bn++] = current;
        } else {
          a[an++] = current;
        }
      }
      current = 0;
    } else {
      ++current;
    }
  }
  if (current > 0) {
    if (current == n) {
      printf("%d\n", 0);
      return;
    }
    b[bn++] = current;
  }
  if (bn == 0) b[0] = b[1] = 0;
  if (bn == 1) b[1] = 0;
  bn = 2;
  int saved = 0;
  std::sort(a, a + an);
  std::sort(b, b + bn);
  int timeline = 0;
  for (int i = an - 1; i >= 0;) {
    int left_middle = a[i] - 2 * timeline;
    int left = b[0] - timeline;
    int right = b[1] - timeline;
    if (left <= 0 && right <= 0 && left_middle <= 0) break;

    if (left <= 0 && right <= 0) {
      saved += 1;
      ++timeline;
      left_middle -= 1;
      if (left_middle > 0) {
        saved += left_middle - 1;
        ++timeline;
      }
      --i;
      continue;
    }
    if (left_middle <= 0) {
      if (left > 0) {
        saved += left;
        b[0] = 0;
        ++timeline;
        continue;
      }
      b[1] = 0;
      saved += right;
      ++timeline;
      continue;
    }
    if ((left_middle > 3 && maxx(left, 0) + maxx(right, 0) - 1 <= left_middle - 1)) {
      saved += left_middle - 1;
      timeline += 2;
      --i;
      continue;
    }
    if (left > right) {
      saved += left;
      ++timeline;
      b[0] = 0;
      continue;
    }
    saved += right;
    ++timeline;
    b[1] = 0;
    continue;
  }
  if (b[0] - timeline > 0) {
   saved += b[0] - timeline;
   ++timeline;
  }
  if (b[1] - timeline > 0) {
   saved += b[1] - timeline;
   ++timeline;
  }
  printf("%d\n", n - saved);
  return;
}

int main() {
  int tests;
  scanf("%d", &tests);
  while (tests--) gogo();
 return 0;
}