#include<bits/stdc++.h>
 using namespace std;
#define int long long
#define ll long long
 int suf[200005]={};
    void solve()
 {
    int n;
    cin>>n;
    string s;
    cin>>s;
    s=" "+s;
    suf[n+1]=0;
    for(int i=n;i>=1;i--)
    {
       suf[i]=suf[i+1]+(s[i]=='0');
    }
    int ans=0;
    for(int i=n;i>=1;i--)
    {
        //suf[i]=suf[i+1];
        if(s[i]=='1'&&suf[i+1]==0)
        {
            suf[i]++;
            continue;
        }
        if(s[i]=='1'&&suf[i+1]>0)
        {
            ans+=i;
            //cout<<"i "<<i<<'\n';
            suf[i]=max(suf[i]-1,0ll);
        }

    }
    cout<<ans<<'\n';


 }
signed main()
{
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);
    int t;
    cin>>t;
    while(t--)
      solve();
    return 0;
}