#include<bits/stdc++.h>

using namespace std;

const int MAXN = 1e6 + 10;

int n;
string s;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int te;	cin >> te;
	while (te--){
		cin >> n >> s;
		int ans = 0;
		for (int l = 0; l < n;){
			if (s[l] == '1'){
				l++;
				continue;
			}
			int r = l;
			while (r < n && s[r] == '0') r++;
			
			int ln = r-l;
			if (r < n) ln--;
			if (l) ln--;
			ln = max(ln, 0);
			ans += ln+1>>1;

			l = r;
		}
		cout << ans << "\n";
	}
	return 0;
}