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
//runda 2B
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
	ios_base::sync_with_stdio(0);

	int t, n, prz, start, bok, bok2, srd, krok, iBok, iSrd, wynik;
	char c;
	vector<int> srodek;
	vector<int> boki;

	cin >> t;
	for(int iT = 0; iT < t; ++iT) {
		srodek.clear();
		boki.clear();
		cin >> n;
		prz = 0;
		start = 1;
		for(int iN = 0; iN < n; ++iN) {
			cin >> c;
			if(c == '0')
				++prz;
			else {
				if(prz) {
					if(start)
						boki.push_back(prz);
					else
						srodek.push_back(prz);
					prz = 0;
				}
				start = 0;
			}
		}
		if(prz)
			boki.push_back(prz);
		sort(srodek.begin(), srodek.end(), greater<int>());
		sort(boki.begin(), boki.end(), greater<int>());

		if(srodek.empty() && boki.size() == 1 && boki[0] == n)
			cout << "0" << endl;
		else {

			if(srodek.empty() && boki.empty())
				cout << n << endl;
			else {

				krok = 0;
				iBok = 0;
				iSrd = 0;
				wynik = 0;
				while(1) {
					bok2 = -10;
					if(iBok >= (int)boki.size())
						bok = -10;
					else {
						bok = boki[iBok] - krok;
						if((boki.size()) == 2 && !iBok)
							bok2 = boki[1] - krok;
					}
					if(!bok)
						bok = -10;
					if(iSrd >= (int)srodek.size())
						srd = -10;
					else
						srd = srodek[iSrd] - 2 * krok;
					if(bok <= 0 and srd <=0)
						break;


					if((bok2 == 3) && (bok == 3) && (srd == 5)) {
						wynik += (bok + bok2 - 1);
						++iBok;
						++iBok;
						++krok;
						++krok;
					}

					else {

						if((bok == 1) and (srd > 0)) {
							bok = -10;
							++iBok;
						}

						if((bok == 2) and (srd > 3)) {
							bok = -10;
							++iBok;
						}

						if((bok + 1) >= srd) {
							wynik += bok;
							++iBok;
							++krok;
						} else
							if(srd > 2) {
								wynik += (srd - 1);
								++iSrd;
								++krok;
								++krok;
							}
							else {
								wynik += 1;
								++iSrd;
								++krok;
							}
					}
				}
				cout << n - wynik << endl;
			}
		}
	}
	return 0;
}