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

using ll = long long;

char s[100001];

int solve(int n) {
  if (n == 1) {
    return s[0] == '0';
  }
  deque<pair<int, int>> v;
  for (int i = 0; i < n;) {
    if (s[i] == '0') {
      int j = i + 1;
      while (j < n && s[j] == '0') {
        j++;
      }
      v.emplace_back(j-i, 2);
      i = j;
    } else {
      i++;
    }
  }
  if (v.empty()) {
    return 0;
  }
  if (s[0] == '0') {
    v.front().second--;
  }
  if (s[n-1] == '0') {
    v.back().second--;
  }
  if (v.back().second == 0) {
    return n;
  }
  vector<int> ones;
  if (v.front().second == 1) {
    ones.push_back(v.front().first);
    v.pop_front();
  }
  if (!v.empty() && v.back().second == 1) {
    ones.push_back(v.back().first);
    v.pop_back();
  }
  if (ones.size() == 2 && ones[0] < ones[1]) {
    swap(ones[0], ones[1]);
  }
  sort(v.begin(), v.end(), greater<pair<int, int>>());
  int res = 0;
  int days = 0;
  for(int i = 0, j = 0; i < v.size() || j < ones.size();) {
    if (i == v.size()) {
      if (ones[j] > days) {
        res += ones[j] - days;
        days++;
      }
      j++;
    } else if (j == ones.size()) {
      int r = v[i].first - 2 * days;
      if (r == 1 || r == 2) {
        res++;
        days++;
      } else if (r > 2) {
        res += v[i].first - 2 * days - 1;
        days += 2;
      }
      i++;
    } else {
      if (v[i].first - 2 * days - 2 > ones[j] - days) {
        int r = v[i].first - 2 * days;
        if (r == 1 || r == 2) {
          res++;
          days++;
        } else if (r > 2) {
          res += v[i].first - 2 * days - 1;
          days += 2;
        }
        i++;
      } else {
        if (ones[j] > days) {
          res += ones[j] - days;
          days++;
        }
        j++;
      }
    }
  }
  return res;
}

int main() {
  int z;
  scanf("%d", &z);
  while (z--) {
    int n;
    scanf("%d", &n);
    scanf("%s", s);
    printf("%d\n", n - solve(n));
  }
}