#include <bits/stdc++.h>
using namespace std;
using ll = long long;
string remove(string s, int i) {
  s.erase(s.begin() + i);
  char last = s.back();
  while (!s.empty() && s.back() == last) {
    s.pop_back();
  }
  return s;
}
vector<string> get_all_poss(string s) {
  int n = s.size();
  vector<string> ans;
  for (int i = 0; i < n; ++i) {
    ans.push_back(remove(s, i));
  }
  return ans;
}
int brute(string s, int n) {
  reverse(s.begin(), s.end());
  queue<string> q;
  int step = 0;
  q.push(s);
  while (!q.empty()) {
    int sz = q.size();
    while (sz--) {
      string p = q.front();
      q.pop();
      for (string out : get_all_poss(p)) {
        if (!out.empty()) q.push(out);
      }
    }
    ++step;
  }
  return step;
}
int solve(string s, int n) {
  if (n == 1) return 1;
  vector<bool> deleted(n, false);
  int i = 0, step = 0, j = 0;
  bool checked_all_consecutive = false;
  while (i < n) {
    if (!checked_all_consecutive) {
      while (j + 1 < n && s[j + 1] != s[j]) {
        ++j;
      }
      deleted[j] = true;
      if (j == n - 1) {
        checked_all_consecutive = true;
        --j;
      } else {
        ++j;
      }
    } else {
      while (deleted[j]) --j;
      deleted[j--] = true;
    }
    while (i < n && deleted[i]) ++i;
    if (j <= i && checked_all_consecutive) {
      ++step;
      break;
    }
    deleted[i] = true;
    for (int k = i + 1; k < n; ++k) {
      if (!deleted[k] && s[k] != s[i]) break;
      if (deleted[k]) continue;
      deleted[k] = true;
    }
    while (i < n && deleted[i]) ++i;
    j = max(j, i);
    ++step;
  }
  return step;
}
int rand(int min, int max) {
  int range = max - min + 1;
  int num = rand() % range + min;
  return num;
}
string random_bin_str(int n) {
  string ans = "";
  while (n--) {
    ans.push_back(rand() % 2 ? '1' : '0');
  }
  return ans;
}
void test_case() {
  while (true) {
    int n = rand(1, 15);
    string r = random_bin_str(n);
    cout << ("r") << " is " << (r) << endl;
    int expected = brute(r, n);
    int actual = solve(r, n);
    if (expected != actual) {
      cout << ("expected") << " is " << (expected) << endl;
      cout << ("actual") << " is " << (actual) << endl;
      break;
    }
  }
}
int main() {
  bool debug = false;
  if (debug) {
    test_case();
    return 0;
  }
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    string s;
    cin >> s;
    cout << solve(s, n) << "\n";
  }
}
