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
132
133
134
135
136
137
138
139
140
141
142
143
144
#include <iostream>
#include<algorithm>
using namespace std;
long long tab[1000001];
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
	cout.tie(0);
    long long dlugosc_miasta, liczba_testow,zaraza=0,dzielnica=0, wartosc_miasto_l = 0, wartosc_miasto_p =0,dzien=0,x=0;
	bool skrajne_miasto_l = 0, skrajne_miasto_p = 0, zmienione_l = false, zmienione_p = false;
	
    string miasto;
    cin>>liczba_testow;
    for(int i=0;i<liczba_testow;i++)
    {
        cin>>dlugosc_miasta;
        cin>>miasto;
        if(miasto[0] == '1')
        {
        	skrajne_miasto_l = true;
		}
		if(miasto[dlugosc_miasta-1] == '1' && dlugosc_miasta != 1)
		{
			skrajne_miasto_p = true;
			
		}
		for(int i=0; i<dlugosc_miasta; i++)
		{
			if(miasto[i] == '1')
			{
				zaraza++;
				if(tab[dzielnica] != 0)
				{
				dzielnica++;
				}
			}
			else
			{
				tab[dzielnica]=tab[dzielnica]+1;
			}
		}
		if(dzielnica ==0) cout<<zaraza<<endl;
		else
		{
			
		if(tab[dzielnica] == 0) dzielnica--;
		if(skrajne_miasto_l == false)
		{
			x=1;
			wartosc_miasto_l =tab[0];
		}
		else
		{
			zmienione_l = true;
		}
		if(skrajne_miasto_p == false)
		{
			wartosc_miasto_p =tab[dzielnica];
			dzielnica--;
		}
		else
		{
			zmienione_p = true;
		}
		
		sort(tab+x, tab+dzielnica+1);
		
		if(skrajne_miasto_l == false && skrajne_miasto_p == false)
		{
			wartosc_miasto_l=max(wartosc_miasto_l,wartosc_miasto_p);
			wartosc_miasto_p=min(wartosc_miasto_l,wartosc_miasto_p);
		}
	//	for(int i=x;i<=dzielnica;i++)
	//	{
	//		cout<<tab[i]<<" ";
	//	}
	//	cout<<endl;
	
			
		for(int i=dzielnica; i>=x; i--)
		{
			if(wartosc_miasto_l-dzien > tab[i]-dzien*2 && zmienione_l == false)
			{
				if(wartosc_miasto_l-dzien>0)zaraza=zaraza+dzien;
				else zaraza=zaraza+wartosc_miasto_l;
				zmienione_l = true;
				dzien++;
			//	cout<<"l: "<<zaraza<<endl;
			}
			if(wartosc_miasto_p-dzien > tab[i]-dzien*2 && zmienione_p == false)
			{
				if(wartosc_miasto_p-dzien>0)zaraza=zaraza+dzien;
				else zaraza=zaraza+wartosc_miasto_p;
				zmienione_p = true;
				dzien++;
			//	cout<<"p: "<<zaraza<<endl;
			}
				if(tab[i]-dzien*2>0)
				{
				zaraza=zaraza+dzien*2;	
					if(tab[i]-(dzien*2+1)>0)
					{
					zaraza++;
				 	dzien=dzien+2;
					}
					else
					{
						dzien++;
					}
				} 
				else
				{
				zaraza=zaraza+tab[i];
				dzien++;
				}
		//	cout<<dzien<<" "<<zaraza<<endl;
			
		}
			if(zmienione_l == false)
			{
				if(wartosc_miasto_l-dzien>0)zaraza=zaraza+dzien;
				else zaraza=zaraza+wartosc_miasto_l;
				zmienione_l = true;
				dzien++;
			//	cout<<"l: "<<zaraza<<endl;
			}
			if(zmienione_p == false)
			{
				if(wartosc_miasto_p-dzien>0)zaraza=zaraza+dzien;
				else zaraza=zaraza+wartosc_miasto_p;
				zmienione_p = true;
				dzien++;
				//cout<<"p: "<<zaraza<<endl;
			}
		cout<<zaraza<<endl;
		}
		for(int i=0; i<dlugosc_miasta; i++)
		{
			tab[i]=0;
		}
		zaraza=0,dzielnica=0, wartosc_miasto_l = 0, wartosc_miasto_p =0,dzien=0,x=0, skrajne_miasto_l = 0, skrajne_miasto_p = 0, zmienione_l = false, zmienione_p = false;
	}
return 0;
}