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
145
#include <iostream>
#include <queue>

// #define DEBUG_M
#ifdef DEBUG_M
#define DEBUGF(...) fprintf(stderr, __VA_ARGS__)
#define DEBUG(expr) expr
#else
#define DEBUGF(...)
#define DEBUG(expr)
#endif

using namespace std;

int simulate(priority_queue<int> &mids, priority_queue<int> &sides) {
	int time = 0;
	int saved = 0;

	for (;;) {
		if (mids.empty() && sides.empty()) {
			break;
		} else if (mids.empty() && !sides.empty()) {
			int willSave = sides.top() - time;
			if (willSave > 0) {
				saved += willSave;
				time++;
				sides.pop();
			} else {
				break;
			}
		} else if (/* !mids.empty() && */ sides.empty()) {
			int midsSize = mids.top() - 2*time;
			if (midsSize <= 0) {
				break;
			} else if (midsSize == 1) {
				saved++;
				time++;
			} else {
				saved += midsSize - 1;
				time += 2;
			}			
			mids.pop();
		} else /* if (!mids.empty && !sides.empty()) */ {
			int midsSize = mids.top() - 2*time;
			int willSaveMids;
			int timeMids;
			if (midsSize > 1) {
				willSaveMids = midsSize-1;
				timeMids = 2;
			} else if (midsSize == 1) {
				willSaveMids = 1;
				timeMids = 1;
			} else {
				willSaveMids = -1;
				timeMids = 2; // Should never be used
			}
			int willSaveSides = sides.top() - time;
			DEBUGF("t: %d; m.t: %d; mS: %d; wSM: %d; tM: %d; s.t: %d; wSS: %d;\n",
						 time, mids.top(), midsSize, willSaveMids, timeMids, sides.top(), willSaveSides);
			if (willSaveSides <= 0 && willSaveMids <= 0) {
				break; 
			} else if (willSaveSides >= willSaveMids) {
				saved += willSaveSides;
				time++;
				sides.pop();
			} else {
				saved += willSaveMids;
				time += timeMids;
				mids.pop();
			}
		}
	}
	
	return saved;
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int t;
	cin >> t;
	for (;t--;) {
		int n;
		cin >> n;
		string str;
		cin >> str;

		int sizeBegin = 0;
		int sizeEnd = 0;
		priority_queue<int> mids;
		int idx = 0;
		for (;str[idx] == '0' && idx < n; idx++);

		sizeBegin = idx;
		if (idx++ == n) { // Nie ma żadnych jedynek
			puts("0");
			continue;
		}

		for(; idx < n; idx++) {
			if (str[idx] == '1') {
				if (sizeEnd) {
					mids.push(sizeEnd);
					sizeEnd = 0;
				}
			} else {
				sizeEnd++;
			}
		}

		priority_queue<int> sides;
		if (sizeBegin == sizeEnd && sizeBegin) { // BODGED EDGE CASE
			mids.push(2*sizeBegin);
		} else {
			if (sizeBegin)
				sides.push(sizeBegin);
			if (sizeEnd)
				sides.push(sizeEnd);
		}
#ifdef DEBUG_M
		{
			auto tmp = mids;
			fprintf(stderr, "mids: ");
			for (;tmp.size();) {
				fprintf(stderr, "%d ", tmp.top());
				tmp.pop();
			}
		}
		{
			auto tmp = sides;
			fprintf(stderr, "\nsides: ");
			for (;tmp.size();) {
				fprintf(stderr, "%d ", tmp.top());
				tmp.pop();
			}
		}
		putc('\n', stderr);
#endif
		
		int saved = simulate(mids, sides);
		DEBUGF("saved: %d\n", saved);
		printf("%d\n", n - saved);
	}
}