#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define vi vector<int>
#define pb push_back
#define fr_z(start,end) for(int z=start;z<end;z++)
#define fr_o(start,end) for(int o=start;o<end;o++)
#define all(m) m.begin(),m.end()
#define mp make_pair
#define fa_io std::ios::sync_with_stdio(false); cin.tie(NULL)

pair<int,int> totct[100000];
int len[100000],prv[100000];

int main()
{
    fa_io;
    
    int t,n;
    string s;
    cin>>t;
    while(t--)
    {
        cin>>n;
        cin>>s;
        fr_z(0,n)
            len[z]=0,prv[z]=-1;
        totct[0]=(s[0]=='0')?mp(1,0):mp(0,1);
        fr_z(1,n)
            totct[z]=s[z]=='0'?mp(totct[z-1].first+1,totct[z-1].second):mp(totct[z-1].first,totct[z-1].second+1);
        fr_z(0,n)
        {
            int tz=totct[z].first,to=totct[z].second;
            //cout<<z<<'-'<<tz<<
            fr_o(0,z+1)
            {
                if(to>tz && len[z]<tz+to)
                    len[z]=tz+to,prv[z]=o;
                //cout<<tz<<'-'<<to<<'\n';
                s[o]=='0'?tz--:to--;
            }
        }
        int z=n-1,j,u;
        /*cout<<'\n';
        fr_z(0,n)
            cout<<setw(4)<<len[z]<<' ';*/
        int sm=0;
        while(z>=0)
        {
            if(!len[z])
            {
                z--;
                continue;
            }
            u=z-1;
            bool i=true;
            for(u=z-1;u>z-len[z];u--)
                if(len[u]>=len[z])
                {
                    i=false;
                    break;
                }
            if(i)
                fr_o(z-len[z]+1,z)
                    len[o]=0;
            else
                len[z]=0;
            z--;
        }
        /*cout<<'\n';
        fr_z(0,n)
            cout<<setw(4)<<len[z]<<' ';
        cout<<'\n';
        fr_z(0,n)
            cout<<setw(4)<<prv[z]<<' ';*/
        cout<<accumulate(len,len+n,0)<<'\n';
    }
    
    return 0;
}