#include "bits/stdc++.h"

using namespace std;

using ll = long long;
using ld = long double;

#define all(x) (x).begin(), (x).end()

int main() {
  ios_base::sync_with_stdio(false);

  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    string s;
    cin >> s;

    bool has2 = false;
    for (int i = 0; i + 1 < n; ++i)
      if (s[i] == '0' && s[i + 1] == '0')
        has2 = true;

    vector<int> chunks;
    for (int i = 0, j = 0; i < n; ++i) {
      if (s[i] == '1')
        ++j;
      if (i + 1 == n || s[i] == '0') {
        chunks.push_back(j);
        j = 0;
      }
    }

    int cnt1 = 0;
    for (char ch : s)
      if (ch == '1')
        cnt1++;

    int ans = 0;
    if (has2)
      ans = cnt1;
    else
      ans = cnt1 + *min_element(all(chunks));

    cout << ans << "\n";
  }

  return 0;
}