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
101
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second

int lr(int i,int T,int typ){
	if(typ == 1)
		return i > T ? 1 : 0;
	if(typ == 2){
		if(2 * T >= i)
			return 0;
		else if(i - 2 * T <= 2)
			return 1;
		else 
			return 2;
	}
}

int licz(int i,int T){
	if(2 * T >= i)
		return 0;
	else if(i - 2 * T <= 2)
		return 1;
	else 
		return i - 2 * T - 1 ;
}

void solve(){
	int n;
	string s;
	cin >> n >> s;
	int p;
	p = -1;
	vector<int> t(n+2, 0);
	int gr1,gr2;
	gr1 = gr2 = 0;
	for(int i=0; i<n; i++){
		if(s[i] == '1' && p == -1){
			gr1 = i - p - 1;
			p = i;
		}else if(s[i] == '1'){
			t[i - p - 1]++;
			p = i;
		}
	}
	if(p == -1){
		cout << 0 << "\n";
		return ;
	}
	gr2 = n - p - 1;

	int T = 0;
	int wynik = 0;
	vector<pair<int,int>> q;
	for(int i=n; i; i--){
		for(int j=0; j<t[i]; j++){
			q.push_back({i, T});
			wynik += licz(i,T);
			T += lr(i,T,2);
		}
	}
	if(gr2 > gr1)
		swap(gr1,gr2);
	reverse(q.begin(), q.end());
	int mw = max(gr1 - T, 0);
	int mI = -1;
	int rem = 0;
	for(int i=0; i<q.size(); i++){
		rem += licz(q[i].F,q[i].S) - licz(q[i].F,q[i].S+1);
		if(mw <= max(gr1 - q[i].S, 0) - rem){
			mw = max(gr1 - q[i].S, 0) - rem;
			mI = i;
		}
	}
	wynik += mw;
	if(mI != -1){
		T = q[mI].S + 1;
		for(int i=mI; i>=0; i--){
			q[i] = {q[i].F, T};
			T += lr(q[i].F,T,2);
		}
	}else
		T++;
	mw = max(gr2 - T, 0);
	rem = 0;
	for(int i=0; i<q.size(); i++){
		rem += licz(q[i].F,q[i].S) - licz(q[i].F,q[i].S+1);
		if(mw <= max(gr2 - q[i].S, 0) - rem){
			mw = max(gr2 - q[i].S, 0) - rem;
		}
	}
	wynik += mw;
	cout << n - wynik << "\n";
}

int main(){
	int Q;
	cin >> Q;
	while(Q--)
		solve();
}