#include <queue>
#include <iostream>

using namespace std;


int test() {
  int n;
  cin >> n;
  priority_queue<int> s1;
  priority_queue<int> s2;
  int score = 0;
  string s;
  cin >> s;

  for (int i = 0; i < n; i++) {
    if (s[i] == '1') {
      continue;
    }
    int j = i;
    while (j < n && s[j] == '0') j++;

    if (i == 0 && j == n) {
      return 0;
    }

    int ln = j - i;
    if (i == 0 || j == n) {
      s1.push(ln);
    } else {
      s2.push(ln);
    }

    i = j - 1;
  }


  int turn = 0;
  while (turn < n) {
    int s1t = s1.empty() ? 0 : max(0, s1.top() - turn);
    int s2t = s2.empty() ? 0 : max(0, s2.top() - 2 * turn);
    if (s1t == 0 && s2t == 0) break;

    if (s1t >= (s2t + 1) / 2) {
      score += s1t;
      s1.pop();
    } else {
      score++;
      s2.pop();
      s1.push(s2t - 1 + turn);
    }

    turn++;
  }

  return n - score;
}

int main() {
  int t;
  cin >> t;
  while (t--) {
    cout << test() << "\n";
  }
}