#include <iostream>
#include <set>

using namespace std;


int main() {
	ios_base::sync_with_stdio(0);
	
	int t;
	cin>>t;
	
	for (int l = 0; l < t; l++) {
		int n;
		cin>>n;
		string s;
		cin>>s;
		
		multiset<int> jed;
		multiset<int> dwa;

		int pocz = 0;
		int kon = 0;
		while (kon < s.length()) {
			while (pocz < s.length() && s[pocz] == '1') {
				pocz++;
			}
			if (pocz == s.length()) break;
			kon = pocz;
			while (kon < s.length() && s[kon] == '0') {
				kon++;
			}
			//err<<pocz<<"-"<<kon<<endl;
			if (pocz == 0 || kon == s.length() // skrajny przedział traci tylko 1 dziennie
				|| kon - pocz == 1) { // jednoelementowe przedziały otoczone z dwóch stron tracą tylko po 1 dziennie
				jed.insert(kon - pocz);
				//err<<"jed insert "<<jed.size()<<endl;
			}
			else {
				dwa.insert(kon - pocz);
				//err<<"dwa insert "<<dwa.size()<<endl;
			}
			pocz = kon;
		}
		
		////err<<" jed size = "<<jed.size()<<" dwa size = "<<dwa.size()<<endl;
		int dni = 0; // tyle razy już zaszczepiono = tyle razy wirus się rozprzestrzenił
		int ocalone = 0;
		while (!(jed.empty() && dwa.empty())) {
			//err<<"jedynki\n";
			//wypisz(jed, dni);
			
			//err<<"dwojki\n";
			//wypisz(dwa, 2 * dni);
			
			if (jed.empty()) {
				//err<<"BIORE Z DWA\n";
				int pierw = *(--dwa.end());
				dwa.erase(--dwa.end());
				jed.insert(pierw - dni - 1);
				ocalone++;
			}
			
			else if (dwa.empty()) {
				//err<<"BIORE Z JED\n";
				int rozm = *(jed.rbegin()) - dni; // tyle miast ocalimy
				//err<<"rozm = "<<rozm<<endl;
				ocalone += rozm;
				jed.erase(--jed.end());
			}
			else {
				//if (*(jed.rbegin()) - dni >= *(dwa.rbegin()) - 2 * dni || *(dwa.rbegin()) - 2 * dni <= 3) {
				//if (*(jed.rbegin()) - dni > 1) {
				//if (jed.size() > 1 && *(--jed.end()) - dni + *(--(--jed.end())) - dni - 1 > *(--dwa.end()) - 2 * dni - 1) {
				//if ((jed.size() > 1 && *(--jed.end()) + *(--(--jed.end())) > *(--dwa.end())) || *(jed.rbegin()) - dni >= *(dwa.rbegin()) - 2 * dni) {
				if (2 * (*(jed.rbegin()) - dni) >= *(dwa.rbegin()) - 2 * dni) {
					//err<<"BIORE Z JED\n";
					int rozm = *(jed.rbegin()) - dni; // tyle miast ocalimy
					//err<<"rozm = "<<rozm<<endl;
					ocalone += rozm;
					jed.erase(--jed.end());	
				}
				else {
					//err<<"BIORE Z DWA\n";
					int pierw = *(--dwa.end());
					dwa.erase(--dwa.end());
					jed.insert(pierw - dni - 1);
					ocalone++;					
				}
			}
			
			dni++;
			// wirus się rozprzestrzenia
			
			// usuwamy te, które po rozprzestrznieniu nie będą istnieć 
			/*
			for (set<int>::iterator it = dwa.begin(); it != dwa.end() && *it <= 2 * dni; it++) { // aktualny rozmiar 0
				dwa.erase(it);
			}*/
			dwa.erase(2 * dni); // (2 * dni - 1) zostało wcześniej przeczucone do jed
			/*
			for (set<int>::iterator it = dwa.begin(); it != dwa.end() && *it <= 2 * dni + 1; it++) { // aktualny rozmiar 1
				dwa.erase(it);
				jed.insert(*it - dni);
			}*/
			int ile = dwa.count(2 * dni + 1);
			dwa.erase(2 * dni + 1);
			for (int j = 0; j < ile; j++) {
				jed.insert(dni + 1);
			}
			
			/*
			for (set<int>::iterator it = jed.begin(); it != jed.end() && *it <= dni; it++) {
				jed.erase(it); 
			}*/
			jed.erase(dni);
		}
		//err<<"ocalone "<<ocalone<<endl;
		cout<<n - ocalone<<"\n";
	}
}