#include <iostream>
#include <queue>

namespace MF {
int n, s, t;
struct Edge {
  int u, v, c, nxt;
} edges[20000007];
int ecnt;
int head[1000007];
void _addedge(int u, int v, int c) {
  edges[ecnt].u = u, edges[ecnt].v = v, edges[ecnt].c = c;
  edges[ecnt].nxt = head[u], head[u] = ecnt, ++ecnt;
}
void addedge(int u, int v, int c) { _addedge(u, v, c), _addedge(v, u, 0); }
int dis[1000007];
int cur[1000007];
bool BFS() {
  for (int i = 1; i <= n; ++i) {
    dis[i] = +0x3b9aca00;
    cur[i] = head[i];
  }
  std::queue<int> q;
  dis[s] = 0, q.push(s);
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (int e = head[u]; e != -1; e = edges[e].nxt) {
      if (edges[e].c != 0 && dis[u] + 1 < dis[edges[e].v]) {
        dis[edges[e].v] = dis[u] + 1, q.push(edges[e].v);
      }
    }
  }
  return dis[t] != +0x3b9aca00;
}
int sF;
int dfs(int u, int fl) {
  if (u == t) {
    sF += fl;
    return fl;
  }
  int rf = fl;
  for (int& e = cur[u]; e != -1; e = edges[e].nxt) {
    if (edges[e].c != 0 && dis[edges[e].v] == dis[u] + 1) {
      int f = dfs(edges[e].v, std::min(fl, edges[e].c));
      fl -= f, edges[e].c -= f, edges[e ^ 1].c += f;
      if (fl == 0) {
        return rf;
      }
    }
  }
  return rf - fl;
}
void init(int _n, int _s, int _t) {
  n = _n, s = _s, t = _t;
  for (int i = 1; i <= n; ++i) {
    head[i] = -1;
  }
  ecnt = 0;
}  
int Dinic() {
  sF = 0;
  while (BFS()) {
    dfs(s, +0x3b9aca00);
  }
  return sF;
}
};

void solve() {
  int n;
  std::string s;
  std::cin >> n >> s;
  MF::init(n + 2, 1, 2);
  int cc = 0;
  for (int i = 0; i < n; ++i) {
    if (s[i] == '1') {
      MF::addedge(1, i + 3, 1);
      ++cc;
    } else {
      MF::addedge(i + 3, 2, 1);
    }
    for (int j : {i - 1, i + 1}) {
      if (0 <= j && j < n) {
        if (s[i] == '1' && s[j] == '0') {
          MF::addedge(i + 3, j + 3, 1);
        }
      }
    }
  }
  int f = MF::Dinic();
  std::cout << cc * 2 - f << '\n';
}
int main() {
  std::cin.tie(nullptr)->sync_with_stdio(false);
  int t;
  std::cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}