1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
#include <bits/stdc++.h>

using namespace std;

int main(){
	ios_base::sync_with_stdio(0);
	int t; cin>>t;
	while(t--){
		int n; cin>>n;
		string s; cin>>s;
		int poprz = -1;
		vector<int> inp;
		int x1, x2;
		for(int i = 0; i < n; i++){
			if(s[i]=='1'){
				if(poprz==-1){
					x1 = i;
				}else if(poprz+1!=i) {
					inp.push_back(i-poprz-1);
				}
				poprz = i;
			}
		}
		if(poprz==-1){
			cout<<0<<'\n';
			continue;
		}
		sort(inp.begin(), inp.end());
		reverse(inp.begin(), inp.end());
		while(inp.size()<=n) inp.push_back(0);
		x2 = n-poprz-1;
		if(x2>x1) swap(x1, x2);
		vector<vector<int>> dp(n, vector<int>(3, -1e9));
		//cout<<x1<<" "<<x2<<'\n';
		for(int i = 0; i < n; i++){
			//case 1
			dp[i][0] = 0;
			if(i>=1){
				if(i>=2) dp[i][0] = dp[i-2][0];
				int pt = (i)/2;
				int dlg = inp[pt]-(i-1)*2;
				dp[i][0] += max(0, dlg-1);
			}
			int pt2 = (i+1)/2;
			int dlg2 = inp[pt2]-(i)*2;
			int tmp = 0;
			if(dlg2==1){
				if(i>=1) tmp = dp[i-1][0];
				tmp++;
			}
			dp[i][0] = max(dp[i][0], tmp);
			//case 2
			pt2 = (i)/2;
			dlg2 = inp[pt2]-(i)*2;
			if(dlg2==1){
				if(i>=1) dp[i][1] = dp[i-1][1];
				dp[i][1] +=1;
			}
			int pt = (i-1)/2;
			int dlg = inp[pt]-(i-1)*2;
			if(i>=2){
				dp[i][1] = max(0, dlg-1);
			       	dp[i][1] += dp[i-2][1];
			}	
			dp[i][1] = max(dp[i][1], i>0?dp[i-1][0]:0+max(0, x1-i));
			pt2 = (i)/2;
			dlg2 = inp[pt2]-(i)*2;
			tmp = 0;
			if(dlg2==1){
				if(i>=1) tmp = dp[i-1][1];
				tmp++;
			}
			dp[i][1] = max(dp[i][1], tmp);
			if(i>0) dp[i][1] = max(dp[i][1], dp[i-1][1]);
			//case 3
			pt = (i-1)/2;
			if(pt>=0) dlg = inp[pt]-(i-1)*2;
			else dlg = 0;
			if(i>=2){
				dp[i][2] = max(0, dlg-1);
			       	dp[i][2] += dp[i-2][2];
			}
			dp[i][2] = max(dp[i][2], (i>0?dp[i-1][1]:0)+max(0, x2-i));
			pt2 = (i-1)/2;
			dlg2 = inp[pt2]-(i)*2;
			tmp = 0;
			if(dlg2==1){
				if(i>=1) tmp = dp[i-1][2];
				tmp++;
			}
			dp[i][2] = max(dp[i][2], tmp);
			if(i>0) dp[i][2] = max(dp[i][2], dp[i-1][2]);
			//cout<<i<<": "<<dp[i][0]<<" "<<dp[i][1]<<" "<<dp[i][2]<<'\n';
		}

		int maksi = max(dp[n-1][0], max(dp[n-1][1], dp[n-1][2]));
		cout<<n-maksi<<'\n';
	}
	return 0;
}