#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
const long long inf = 0x3f3f3f3f3f3f3f3fll;
using namespace std;
long long gcd(long long a, long long b) {
  if (a == 0) return b;
  return gcd(b % a, a);
}
long long lcm(long long a, long long b) { return (a * b) / gcd(a, b); }
int main(int argc, char* argv[]) {
  ios_base::sync_with_stdio(0);
  cin.tie(NULL);
  long long test;
  cin >> test;
  while (test--) {
    long long n, i, start0 = -1, end0 = -1, start1 = -1, end1 = -1, cnt = 0, x,
                    y, pos;
    cin >> n;
    string s;
    cin >> s;
    vector<long long> v;
    deque<long long> dq;
    for (i = 0; i < n; i++) {
      if (i == 0) {
        if (s[i] == '0') start0 = i;
        if (s[i] == '1') start1 = i;
      } else {
        if (s[i] == '0' && s[i - 1] == '1') start0 = i;
        if (s[i] == '1' && s[i - 1] == '0') start1 = i;
      }
      if (i == n - 1) {
        if (s[i] == '0') end0 = i;
        if (s[i] == '1') end1 = i;
      } else {
        if (s[i] == '0' && s[i + 1] == '1') end0 = i;
        if (s[i] == '1' && s[i + 1] == '0') end1 = i;
      }
      if (start1 != -1 && end1 != -1) {
        v.push_back(end1 - start1 + 1);
        end1 = start1 = -1;
      }
      if (start0 != -1 && end0 != -1) {
        v.push_back(end0 - start0 + 1);
        end0 = start0 = -1;
      }
    }
    reverse(v.begin(), v.end());
    pos = v.size() - 1;
    while (v.size()) {
      bool flag = false;
      for (i = pos; i >= 0; i--) {
        if (v[i] != 1) {
          flag = true;
          break;
        }
      }
      pos = i;
      if (flag) {
        v[pos]--;
      } else {
        cnt += v.size() / 2;
        if (v.size() % 2) cnt++;
        break;
      }
      cnt++;
      if (pos == v.size() - 1) pos--;
      v.pop_back();
    }
    cout << cnt << endl;
  }
  return 0;
}
