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
#include <bits/stdc++.h> //Michał Kuśmirek
using namespace std;     //XIII LO Szczecin

#define FOR(i, a, b) for(int i = (a); i <= (b); ++i)
#define REP(i, n) for(int i = 0; i < (n); ++i)

using ll = long long;
using pii = pair<int, int>;

template<class T> int size(T && a) {
	return (int)(a.size());
}
ostream& operator << (ostream &os, string str) {
    for(char c : str) os << c;
    return os;
}
template <class A, class B> ostream& operator << (ostream &os, const pair<A, B> &p) {
	return os << '(' << p.first << "," << p.second << ')';
}
template <class T> auto operator << (ostream &os, T &&x) -> decltype(x.begin(), os) {
	os << '{';
	for(auto it = x.begin(); it != x.end(); ++it)
		os << *it << (it == prev(x.end()) ? "" : " ");
	return os << '}';
}
template <class T> ostream& operator << (ostream &os, vector<vector<T>> vec) {
    for(auto x : vec)
    	os << "\n  " << x;
    return os;
}
void dump() {}
template <class T, class... Args> void dump(T &&x, Args... args) {
    cerr << x << "; ";
    dump(args...);
}
#ifdef DEBUG
# define debug(x...) cerr << "[" #x "]: ", dump(x), cerr << '\n'
#else 
# define debug(...) 0
#endif

//--------------------------------------------------

void solve() {
	int n; cin >> n;
	string s;
	cin >> s;

	int pref = 0;
	while(pref < n and s[pref] == '0')
		++pref;

	int suf = 0;
	while(suf < n and s[n - 1 - suf] == '0')
		++suf;

	priority_queue<pair<int, int>> Q;
	Q.push(pair(2 * pref, 2));

	if(pref != n)
		Q.push(pair(2 * suf, 2));

	int block = 0;
	FOR(i, pref, n - 1) {
		if(s[i] == '0')
			++block;
		else {
			Q.push(pair(block, 1));
			block = 0;
		}
	}

	int it = 0;
	int ans = 0;
	while(!Q.empty() and 2 * it < Q.top().first) {
		auto [x, p] = Q.top();
		Q.pop();

		int len = (x - 2 * it) / p;
		ans += len;
		++it;

		if(p == 1) {
			if(len > 1)
				--ans;
			++it;
		}
	}

	cout << n - ans << '\n';
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int T; cin >> T;
	while(T--)
		solve();
}