#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int,int>pii;
typedef pair<ll,ll>pll;
typedef pair<ld,ld>pdd;
typedef pair<ll, pair<ll, ll> > plpair;
typedef vector<int> vi;
typedef vector<ll> vl;
#define endl '\n'
#define rep(i, a, b) for (ll i = (a); i <= (b); ++i)
#define per(i, a, b) for(ll i = (a); i >= (b); --i)
#define debug(x) cout<<#x<<": "<<x<<endl
#define lowbit(id) id & (-id)
#define fi first
#define sec second
#define lc id<<1
#define rc id<<1|1
#define sz(x) (int)(x).size()
#define all(t) (t).begin(), (t).end()
#define meh {cout<<"NO"<<endl;return;}
#define yay {cout<<"YES"<<endl;return;}
#define vin(v) for(auto&x:v)cin>>x;
#define print(v) for (auto x: v)cout<<x<<' ';cout<<endl;
#define sqrt(x) sqrtl(x)
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
const ll N = 3e5 + 10;
const int mod = 998244353;

void solve() {
	int n;
    cin >> n;
    string s;
    cin >> s;
    s = '|' + s;
    int dp[n + 5][2];
    int f = 0, zero;
    rep(i, 1, n) {
        if(s[i] == '1') {
            if(f) {
                zero = i - f - 1;
                dp[i][0] = min(dp[f][0] + max(0, zero - max(0, dp[f][0] - 1) - dp[f][0]), dp[f][1] + max(0, zero - dp[f][1] - dp[f][1]));
                dp[i][1] = min(dp[f][0] + max(0, zero - max(0, dp[f][0] - 1) + 1 - dp[f][0]), dp[f][1] + max(0, zero - dp[f][1] + 1 - dp[f][1]));
            }
            else {
                dp[i][0] = i - 1;
                dp[i][1] = i;
            }
            f = i;
        }
    }
    zero = n - f;
    cout << min(dp[f][0] + max(0, zero - max(0, dp[f][0] - 1)), dp[f][1] + max(0, zero - dp[f][1])) << endl;
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int T = 1;
	cin >> T;
	//	cout.flush();
	//		ofstream outfile("C:\\Users\\86187\\OneDrive\\桌面\\1.txt");
	//		outfile << "a[1]=0;a[2]=1;";
	//		ll l = 1e7 + 1;
	//		rep(i, 3, 1e9) {
	//			printf("%lld\n", i);
	//			ll x = (i - 1) * ((a[i - 1] + a[i - 2]) % mod);
	//			x %= mod;
	//			if(i == l) {
	//				outfile << "a[" << i << "]=" << x << ";";
	//			}
	//			if(i == l + 1) {
	//				outfile << "a[" << i << "]=" << x << ";";
	//				l += 1e7;
	//			}
	//		}
	while(T--) {
		solve();
	}
	return 0;
}