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
#include<bits/stdc++.h>
#define ff first
#define ss second
#define mp make_pair
#define pb push_back
using namespace std;
typedef pair<int,int> pp;
int ile2(int v)
{
	if(v<=0)	return 0;
	if(v==1)	return 1;
	return v-1;
}
int ile1(int v)
{
	if(v<=0)	return 0;
	return v;
}
int main()
{
	int t;
	cin>>t;
	for(int qq=0;qq<t;++qq)
	{
		int n;
		cin>>n;
		string s;
		cin>>s;
		vector<pp> prze;
		int co=0;
		int beg=0;
		int b0=-1,b1=-1;
		vector<int> dl;
		for(int i=0;i<n;++i)
		{
			if(s[i]=='1')
			{
				++co;
				if(beg!=i)
				{
					if(beg==0)	b0=i;
					else		dl.pb(i-beg);
				}
				beg=i+1;
			}
		}
		if(co==0)
		{
			printf("0\n");
			continue;
		}
		if(beg<=n-1)	b1=n-beg;

		sort(dl.begin(),dl.end());
		reverse(dl.begin(),dl.end());
//		printf(":\n");
//		for(auto I : dl)	printf("%d ",I);
//		printf("\n");
		int si=(int)dl.size();
		int l0=0,l1=max(0,b0),l2=max(0,b1),l3=max(0,b0+b1-1),wy=0;
//		printf(">>%d %d\n",b0,b1);
		for(int i=0;i<si;++i)
		{
//			printf("%d %d %d %d\n",l0,l1,l2,l3);
			int t0=0,t1=0,t2=0,t3=0;
			//ile czasu mineło dla 0

			t0=l0+ile2(dl[i]-2*(2*i));

			t1=max({l1+ile2(dl[i]-2*(2*i+1)),t0+ile1(b0-(2*i+2))});
			//									bo zrobiliśmy t0, więc czasu mineło więcej

			t2=max({l2+ile2(dl[i]-2*(2*i+1)),t0+ile1(b1-(2*i+2))});
				
			t3=max({l3+ile2(dl[i]-2*(2*i+2)),t1+ile1(b1-(2*i+3)),t2+ile1(b0-(2*i+3))});

			l0=t0;
			l1=t1;
			l2=t2;
			l3=t3;
		}
//		printf("%d %d %d %d\n",l0,l1,l2,l3);

		printf("%d\n",n-max({l0,l1,l2,l3}));
	}
}