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
#include<bits/stdc++.h>
#define double long double
#define ll long long
using namespace std;

int32_t main(){

	ios::sync_with_stdio(false);cin.tie(NULL);
	
	int z;cin>>z;while(z--){
		
		int n;cin>>n;
		string s;cin>>s;
		vector<double> V;
		double res=0;
		for(char x:s)if(x=='1')res++;
		int i=0,last=-1, v=0;
		while(i<n&&s[i]=='0')i++;
		last=i++;
		while(i<n){
			while(i<n&&s[i]=='0')i++;
			v=i-last-1;
			if(v>0&& i<n){
				V.push_back(v/2.0);
				V.push_back(v/2.0);
		//		cout <<v/2<<" "<<v-v/2<<" ";
			}
			last=i++;
		}
		if(s[0]=='0'){
			i=0;
			while(i<n&&s[i]=='0')i++;
			V.push_back(i);
	//		cout << i<<" ";
		}
		if(s[n-1]=='0'&&res){
			i=n-1;
			while(i>=0&&s[i]=='0')i--;
			V.push_back(n-1-i);
		//	cout << n-1-i<<" ";
		}
	//	cout << endl;
		res=0;
		sort(V.rbegin(),V.rend());
//		for(auto x:V)cout << x<<" ";cout<<endl;
		for(int i=0;i<V.size();i++)
			if(V[i]-i>0)	res+=V[i]-i;
			else 			break;
	//	cout << n-res<<endl;
	
		if(res != (int)res) res += 0.5;
	//	cout << res<<" ";
		cout << n-res<<endl;
	}
}