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
#include <bits/stdc++.h>
#include <chrono>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace chrono;
using namespace __gnu_pbds;
#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma,tune=native")
//#pragma GCC target("sse,sse2,sse3,mmx,abm,tune=native") // for szkopul and sio only
typedef long long lld;
typedef double lf;
typedef long double llf;
typedef pair<int,int> pii;
typedef pair<lld,lld> pll;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> oset;
#define For(i,s,a) for(lld i = (lld)s; i < (lld)a; ++i)
#define rpt(s, it) for(auto it = s.begin(); it != s.end(); ++it)
#define brpt(s, it) for(auto it = s.rend(); it != s.rbegin(); --it)
#define pb push_back
#define eb emplace_back
#define ff first
#define dd second
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define make_unique(x) (x).erase( unique(all(x)), (x).end())
#define popcnt(x) __builtin_popcount(x)
#define sz size()
#define time_since duration_cast< milliseconds >(system_clock::now().time_since_epoch())
 
template<typename Ta, typename Tb>
ostream & operator <<(ostream & os, pair<Ta, Tb> x){
	return os << x.ff << " " << x.dd;
}

const int N = 1e5 + 1;
char s[N];
vector<pii>c;

bool cmp(pii a, pii b) {
	if(a.dd == b.dd)
		return a.ff > b.ff;
	if(a.dd > b.dd)
		return !cmp(b, a);
	//return max(a.ff - 2, 0) + max(b.ff - 1, 0) > a.ff + max(b.ff - 3, 0);
	//cout << a << " " << b << endl;
	return a.ff * 2 > b.ff;
}

void solve(void) {
	int n;
	scanf("%d", &n);
	scanf("%s", s);
	c.clear();
	vector<pii>().swap(c);
	
	int d = s[0] == '0';
	while(d < n && s[d] == '0')
		++d;
	if(d == n) {
		printf("%d\n", 0);
		return;
	}
	
	int u = s[n - 1] == '0';
	while(s[n - 1 - u] == '0')
		++u;
	
	c.pb({d, 1});
	c.pb({u, 1});
	//cout << d << " " << u << endl;
	For(i, d + 1, n - u) {
		if(s[i] == '1')
			continue;
		int tmp = 1;
		while(i + tmp < n - u && i + tmp < n && s[i + tmp] == '0')
			++tmp;
		//cout << i << " e " << tmp << endl;
		c.pb({tmp, 2});
		i = i + tmp;
	}
	sort(c.begin(), c.end(), cmp);
	//for(auto s : c)
	//	cout << s.ff << " " << s.dd << endl;
	int wyn = 0, tim = 0;
	For(i, 0, c.sz) {
	//	cout << c[i].ff << " hmm " << c[i].dd << endl;
		if(c[i].dd == 2) {
			if(c[i].ff > tim * 2 + 1 && c[i].ff - tim * 2 - 1 == 1) {
				wyn += 1;
				tim++;
			}
			else if(c[i].ff > tim * 2 + 1) {
	//			cout << "B1" << endl;
				wyn += c[i].ff - tim * 2 - 1,
				tim += 2;
			}
			else if(c[i].ff > tim * 2) {
	//			cout << "B2" << endl;
				wyn += c[i].ff - tim * 2,
				++tim;
			}
		} else {
			if(c[i].ff > tim) {
	//			cout << "B3" << endl;
				wyn += c[i].ff - tim;
				++tim;
			}
		}
	}
	printf("%d\n", n - wyn);
}

int32_t main(void){
	int t;
	scanf("%d", &t);
	while(t--)
		solve();
}