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
#include <bits/stdc++.h>
#define boost ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define debug(x) cerr << #x << " " << x << endl
#define int long long
#define st first
#define nd second

using namespace std;

const int N(1e6 + 13);
const int MAX(LLONG_MAX);

int n, q, cnt, zeit, it1, it2, healthy, tmp;
vector <int> areas2, areas1;
bool flag;
string s;

int32_t main() {
  boost;
  cin >> q;
  while (q--) {
    cin >> n;
    cin >> s;
    for (int i = 0; i < n; i++) {
      cnt = 0;
      while (i < n && s[i] == '0') {
        cnt++;
        i++;
      }
      if (cnt > 0) {
        areas2.push_back(cnt);
      }
    }

    if (s[0] == '0') {
      areas1.push_back(areas2[0]);
      areas2.erase(areas2.begin());
    }
    if (s[n - 1] == '0' && (areas1.empty() || areas1[0] != n)) {
      areas1.push_back(areas2.back());
      areas2.pop_back();
    }

    sort(areas1.begin(), areas1.end(), greater<int>());
    sort(areas2.begin(), areas2.end(), greater<int>());

    zeit = 0;
    it1 = 0;
    it2 = 0;
    healthy = 0;

    while (true) {
      if (it1 < areas1.size() && areas1[it1] - zeit <= 0) {
        areas1.clear();
      }
      if (it2 < areas2.size() && areas2[it2] - zeit * 2 <= 0) {
        areas2.clear();
      }

      if (it1 < areas1.size() && it2 < areas2.size()) {
        if (areas1[it1] - zeit + 1 >= areas2[it2] - zeit * 2) {
          healthy += areas1[it1] - zeit;
          it1++;
          zeit++;
        } else {
          tmp = areas2[it2] - zeit * 2;
          if (tmp <= 2) {
            healthy++;
            zeit++;
          } else {
            healthy += tmp - 1;
            zeit += 2;
          }
          it2++;
        }
      } else if (it1 < areas1.size()) {
        healthy += areas1[it1] - zeit;
        it1++;
        zeit++;

      } else if (it2 < areas2.size()) {
        tmp = areas2[it2] - zeit * 2;
          if (tmp <= 2) {
            healthy++;
            zeit++;
          } else {
            healthy += tmp - 1;
            zeit += 2;
          }
          it2++;
      } else {
        break;
      }
    }

    cout << n - healthy << endl;
    areas1.clear();
    areas2.clear();
  }



}