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
#include <iostream>
#include <set>
#include <vector>
#include <algorithm>

using namespace std;

#ifdef _HOME_
    #define DEBUG(x) x
#else
    #define DEBUG(x)
#endif
#define REP(x,n) for(int x=0;x<(n);++x)
#define FOREACH(x,n) for(__typeof(n.begin()) x = (n).begin(); x != (n).end(); ++x)
#define RESULT(x) {cout<<(x);return 0;}

int t,n;
string str;
vector<int> twoways;
vector<int> oneway;

template<typename _T> ostream& operator<<(ostream& os, const vector<_T>& v) {
	bool first=true;
	FOREACH(it, v) {
		if (first) {
			first = false;
		}
		else
			os<<", ";
		os<<*it;
	}
	return os;
}

int solve() {
	cin>>n>>str;
	DEBUG(cerr<<"solve "<<str<<endl;)
	str += 'x'; // guardian
	twoways.clear();
	oneway.clear();
	twoways.reserve(n);
	int i=0;
	if (str[0]=='0') {
		while(str[i]=='0')
			++i;
		oneway.push_back(i);
		DEBUG(cerr<<"starts with oneway "<<i<<endl);
	}
	int infected=0;
	int last1=i;
	while(i<n) {
		while(str[i]=='1') {
			++i;
			++infected;
		}
		last1 = i;
		while(str[i]=='0')
			++i;
		if (i==last1)
			break;
		else if (i==n) {
			oneway.push_back(i-last1);
			DEBUG(cerr<<"ends with oneway "<<(i-last1)<<endl);
		}
		else {
			twoways.push_back(i-last1);
			DEBUG(cerr<<"has twoways "<<(i-last1)<<endl);
		}
	}
	if (infected == 0)
		return 0;
	sort(oneway.begin(), oneway.end(), std::greater<int>());
	sort(twoways.begin(), twoways.end(), std::greater<int>());
	DEBUG(
		cerr << "one way: " << oneway << endl;
		cerr << "two ways: " << twoways << endl;
	)
	vector<int>::iterator i1=oneway.begin(), i2=twoways.begin();
	int round;
	for(round=0;i1!=oneway.end() || i2!=twoways.end();++round) {
		if (i1 != oneway.end() && (i2==twoways.end() || *i1*2>=*i2)) {
			DEBUG(cerr<<"shot one way "<<*i1<<endl);
			infected += min(*i1, round);
			++i1;
		}
		else {
			DEBUG(cerr<<"shot two way "<<*i2<<endl);
			infected += min(*i2, round*2);
			if (*i2 > round*2) {
				if (*i2 > round*2+1)
					++infected;
				++round;
			}
			++i2;
		}
	}
	return infected;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin>>t;
	REP(x,t)
		cout << solve() << endl;
	return 0;
}