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>
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("trapv")

#define st first
#define nd second
#define pb(x) push_back(x)
#define pp(x) pop_back(x)
#define mp(a, b) make_pair(a, b)
#define all(x) (x).begin(), (x).end()
#define rev(x) reverse(all(x))
#define sor(x) sort(all(x))
#define sz(x) (int)(x).size()
#define rsz(x) resize(x)

using namespace std;

///~~~~~~~~~~~~~~~~~~~~~~~~~~

void debug(){cerr<<"\n";}
template <typename H, typename... T>
void debug(H h, T... t) {cerr<<h; if (sizeof...(t)) cerr << ", "; debug(t...);}
#define deb(x...) cerr<<#x<<" = ";debug(x);

///~~~~~~~~~~~~~~~~~~~~~~~~~

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<pii > vii;
typedef vector<ll> vl;
typedef vector<pll> vll;
typedef string str;

#define BOOST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

const int N=2e5+5, INF=1e9+5, mod=1e9+7;

int main(){
	BOOST;
	int T;
	cin>>T;
	while(T--){
		int n;
		cin>>n;
		str s;
		cin>>s;
		int ile=0;
		vector<int> V;
		for(int i=0; i<=n; i++){
			if(i<n && s[i]=='0')ile++;
			else V.pb(ile), ile=0;
			if(V.size() && V.back()==0)V.pp();
		}
		vector<int> V2(V.size(), 2);
		int k=V2.size()*2;
		if(s[0]=='0')V2[0]--, k--;
		if(s.back()=='0')V2.back()--, k--;
		set<pair<int, int> > S;
		int ans=0;
		for(int i=0; i<V.size(); i++){
			ans+=V[i];
			if(V2[i])S.insert(mp((2*V[i])/V2[i], i));
		}
		for(int i=0; S.size(); i++){
			//cout<<"S2: ";
			//for(auto i:S)cout<<i.st<<" "<<i.nd<<", ";
			//cout<<"\n";
			while((*S.begin()).st==2*i+1){
				pii a=*S.begin();
				V2[a.nd]=1;
				V[a.nd]=i+1;
				k--;
				S.erase(S.begin());
				a.st=2*i+2;
				S.insert(a);
			}
			//cout<<"S: ";
			//for(auto i:S)cout<<i.st<<" "<<i.nd<<", ";
			//cout<<"\n";
			pii a=*(S.crbegin());
			S.erase(S.find(a));
			V[a.nd]-=V2[a.nd]*i;
			V2[a.nd]--;
			k--;
			V[a.nd]+=V2[a.nd]*i;
			if(V2[a.nd])S.insert(mp((2*V[a.nd])/V2[a.nd], a.nd));
			ans-=k;
			while(S.size() && (*S.begin()).st<=2*(i+1)){
				k-=V2[(*S.begin()).nd];
				S.erase(S.begin());
			}
		}
		cout<<n-ans<<"\n";
	}
}