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
129
130
131
#include<bits/stdc++.h>
using namespace std;
deque<pair<int, int> > blocks;
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin>>t;
	for(int y =0;y<t;y++)
	{
		int n;
		cin>>n;
		string s="";
		cin>>s;
		int block=0;
		bool isfirst=1;
		int first_block=-1;
		int last_block=-1;
		s+='1';
		for(int i=0;i<s.size();i++)
		{
			//cout<<s[i];
			if(s[i]=='1'&&block>0)
			{
				if(isfirst==1)
				{
					isfirst=0;
					first_block=block;
					block=0;
					continue;
				}
				else
				{
					isfirst=0;
					if(i==s.size()-1)
					last_block=block;
					else
					blocks.push_back({-block, 2});
					block=0;
					continue;
				}
			}
			else if(s[i]=='0')
			block++;
			if(s[i]=='1')
			isfirst=0;
		}
		sort(blocks.begin(), blocks.end());
		//cout<<blocks.size();
	/*	for(int i=0;i<blocks.size();i++)
		{
			cout<<blocks[i].first<<" "<<blocks[i].second<<"\n";
		}*/
		int c=0;
		int res=0;
		bool pop=0;
		while(!blocks.empty()||first_block>-1||last_block>-1)
		{
		//	cout<<first_block<<" "<<last_block<<" "<<blocks.front().first<<" ";
			if(first_block-c<=0)
			first_block=-1;
			if(last_block-c<=0)
			last_block=-1;
			int a;
			if(blocks.size()>0)
			a=-blocks.front().first;
			else
			a=-3;
			a-=c*2+1;
		//	cout<<a<<" "<<first_block-c<<"\n";
			//cout<<a<<"\n";
			if(a<0&&last_block==-1&&first_block==-1)
			break;
			if(first_block>0||last_block>0)
			{
				if(first_block-c>=a-1||last_block-c>=a-1)
				{
					//cout<<"DUPA";
					if(first_block>last_block)
					{
						if(first_block-c<=0)
						{
							first_block=-1;
							last_block=-1;
							continue;
						}
						res+=first_block-c;
						c++;
						first_block=-1;
						continue;
					}
					else
					{
						if(last_block-c<=0)
						{
							first_block=-1;
							last_block=-1;
							continue;
						}
						res+=last_block-c;
						c++;
						last_block=-1;
						continue;
					}
					continue;
				}
			}
			//cout<<a<<" ";
			if(a==0)
			{
				c++;
				blocks.pop_front();
				res++;
				continue;
			}
			if(a<=0)
			{
				blocks.pop_front();
				continue;
			}
			c+=2;
			res+=a;
			blocks.pop_front();
			continue;
		}
		cout<<n-res<<"\n";
		blocks.clear();
	}
}