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

bool bit;
char bt;
int n,t,licz,p,k,tab[100007],wynik;

bool sor(int a,int b)
{
	return a>b;
}
int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	for(int i=0;i<n;i++)
	{
		cin >> t;
		int j=0;
		int iter=0;
		p=0;
		k=0;
		licz=0;
		wynik=0;
		for(;j<t;)
		{
			j++;
			cin >> bt;
			bit=bt-'0';
			if(bit) {p=licz;licz=0;break;}
			licz++;
		}
		if(!p) p=licz;
		licz=0;
		if(p==t) {cout << "0\n";continue;}
		for(;j<t;)
		{
			j++;
			cin >> bt;
			bit=bt-'0';
			if(bit && licz) {tab[iter]=licz;iter++;licz=0;continue;}
			if(!bit) licz++;
		}
		if(!bit) k=licz;
		sort(tab,tab+iter,sor);
		int dzie=0;
		int tabit=0;
		//                            tab[tabit]
		while(p-dzie>0 || k-dzie>0 || tab[tabit]-(2*dzie)>0)
		{
			if(p-dzie>=tab[tabit]-(2*dzie)-2 and p-dzie>0)
			{
				if(p-dzie>=k-dzie)
				{
					wynik+=(p-dzie);
					p=0;
				}
				else
				{
					wynik+=(k-dzie);
					k=0;
				}
				dzie++;
				continue;
			}
			else
			{
				if(k-dzie>=tab[tabit]-(2*dzie)-1 and k-dzie>0)
				{
					wynik+=(k-dzie);
					k=0;
					dzie++;
					continue;
				}
			}
			if(tab[tabit]-(2*dzie)>0)
			{
				if(tab[tabit]-(2*dzie)<=2)
				{
					wynik++;
					tabit++;
					dzie++;
				}
				else
				{
					//if(p+k>tab[0] && p<tab[0] && k<tab[0]) wynik++;
					wynik+=(tab[tabit]-(2*dzie)-1);
					tabit++;
					dzie+=2;
				}
			}
			else break;
		}
		for(int i=0;i<=iter+10;i++)
		{
			tab[i]=0;
		}
		cout << t-wynik << "\n";
	}
	return(0);
}