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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <unordered_set>
#include <queue>

using namespace std;
int a[100000+1];


int main(){
	int t = 0;
	cin >> t;
	while(t--){
		int n = 0;
		cin >> n;
		string s;
		cin >> s;
		int k = 0;
		int start = 0;
		int stop = 0;
		int i = 0;
		while(i < n && s[i]=='0'){
			start++;
			i++;
		}
		while(i < n){
			if(s[i]=='0'){
				a[k]++;
			}
			if(s[i]=='1'){
				k++;
			}
			i++;
		}
		if(s[n-1]=='0' && start < n){
			stop = a[k];
		}
		//cout << k << " k\n";
		
		//cout << start << " " << stop << "\n";
		//for(int x = 0; x < k; ++x){
		//	cout << a[x] << " ";
		//}
		//cout << "\n";
		
		sort(a, a+k, greater<int>());
		
		//for(int x = 0; x < k; ++x){
		//	cout << a[x] << " ";
		//}
		//cout << "\n";
		
		int wynik=n;
		int be=0;
		int ed=k;
		while(ed > be){
			//cout << "abe-1: = " << a[be]-1 << " start: " << start << " " << "stop: " << stop << "\n";
			if( (a[be]-1 >= (start+stop) && start >0 && stop > 0) || (a[be]-2 > start && (stop < 1)) || (a[be]-2 > stop && (start < 1)) || (1 > start && 1 > stop)){
				if(a[be]==1){
					wynik-=1;
				}else{
					wynik-=((a[be]-1)>0?(a[be]-1):0);
				}
				start-=2;
				stop-=2;
				be++;
				int q=be;
				while(q<ed && a[q]>0){
					a[q]-=4;
					q++;
				}
				ed=q;
			}else{
				if(start > stop){
					wynik-=(start>0?start:0);
					start=0;
					stop-=1;
					int q=be;
					while(q<ed && a[q]>0){
						a[q]-=2;
						q++;
					}
					ed=q;
				} else {
					wynik-=(stop>0?stop:0);
					start-=1;
					stop=0;
					int q=be;
					while(q<ed && a[q]>0){
						a[q]-=2;
						q++;
					}
					ed=q;
				}
			}
			//cout << "wynik: " << wynik << "\n";
			//cout << start << " " << stop << "\n";
			//for(int x = 0; x < k; ++x){
			//cout << a[x] << " ";
			//}
			//cout << "\n";
		}
		//cout << "abe-1: = " << a[be]-1 << " start: " << start << " " << "stop: " << stop << "\n";
		//cout << "wynik: " << wynik << "\n";
		//	cout << start << " " << stop << "\n";
		//	for(int x = 0; x < k; ++x){
		//	cout << a[x] << " ";
		//	}
		//	cout << "\n";
		
		
		start = (start>0?start:0);
		stop = (stop>0?stop:0);
		if(start > stop){
			wynik-=start+((stop-1)>0?(stop-1):0);
		}else{
			wynik-=stop+((start-1)>0?(start-1):0);
		}
		for(int x = 0; x < n; ++x){
			a[x]=0;
		}
		cout << wynik << "\n";
	}
	
	return 0;
}