#include<bits/stdc++.h> 
#define I if 
#define E else 
#define W while 
#define F for 
#define R return 
#define S scanf 
#define P printf
using namespace std;int y[100000];int x[100000];
void q(){int n,i,d,t,r,q,w,e,u;char c;S("%d",&n);i=0;d=0;r=0;e=q=u=w=0;W(i<n){S(" %c",&c);I(c=='1'){r++;I(d>0){I(d==i)x[u++]=d;E y[w++]=d;}d=0;}E d++;i++;}I(d==n){P("0\n");R;}I(d>0){x[u++]=d;}sort(x,x+u);sort(y,y+w);t=0;W(w-q+u-e>0){I(w==q){u--;}E I(u==e){I(y[w-1]-2*t-1>0){x[u++]=y[w-1]-2*t-1+t;}w--;}E I(x[u-1]>y[w-1]/2){u--;}E{I(y[w-1]-2*t-1>0){x[u++]=y[w-1]-2*t-1+t;}w--;}r+=2*(w-q)+u-e;t++;W(e<u && x[e]-t==0){e++;}W(q<w && y[q]-2*t<=0){I(y[q]-2*t==-1){r--;}q++;}}P("%d\n",r);}
int main(){int t,i;S("%d",&t);F(i=0;i<t;i++)q();R 0;}