#include <bits/stdc++.h>
using namespace std;

int main() {
  ios_base::sync_with_stdio(false);
  int z;
  cin >> z;
  while (z--) {
    int n;
    cin >> n;
    string s;
    cin >> s;

    int result = 0;

    vector<pair<int, int>> fragments;
    int l=0;
    bool first=true;
    for (char c: s) {
      if (c=='1') {
        ++result;
        if (l > 0)
          fragments.emplace_back(l, first ? 1 : 2);
        l = 0;
        first = false;
      } else {
        ++l;
      }
    }
    if (l > 0)
      fragments.emplace_back(l, 1);

    sort(fragments.begin(), fragments.end(),
      [](pair<int, int> a, pair<int, int> b) {
        return a.first * b.second > b.first * a.second; });

    int t=0;
    for (auto f : fragments) {
      // cerr << f.first << ' ' << f.second << endl;
      int delta = f.second == 2 ? t * 2 + 1 : t;
      if (f.second == 2 && f.first == t * 2 + 1)
        delta--;
      result += min(f.first, delta);
      t += f.second;
    }

    cout << result << endl;
  }
}