//// Practice is the only shortcut idiot
#include <bits/stdc++.h>
#include <cstdlib>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define pb push_back
#define ss second
#define ff first
#define endl "\n"
#define vll vector < ll >
#define all(a)(a).begin(), (a).end()
#define f(i, n) for (ll i = 0; i < n; i++)
#define setbit(x) __builtin_popcount(x)
#define mod 1000000007
using namespace std;
using namespace __gnu_pbds;
/*

*/
void solve(){
    ll n;cin>>n;
    string s;cin>>s;
    ll x=count(all(s),'1');
    if(x%2==1){
        cout<<-1<<endl;
        return;
    }
    vector<ll>v;
    ll cnt=0,i=0;
    while(n>i){
        if(s[i]=='1'){
            cnt++;
        }else{
            if(cnt>0)v.pb(cnt);
            cnt=0;
        }
        i++;
    }
    if(s[n-1]=='1'){
        v.pb(cnt);
    }
    sort(all(v));
    if(n-x==0){
        cout<<x/2<<endl;
        return;
    }
    if(v.size()==0){
        cout<<0<<endl;
        return;
    }
    priority_queue<ll>p;
    for(auto i:v){
        p.push(i);
    }
    ll ans=0;
    while(p.size()>1){
        ll x=p.top();
        p.pop();
        ll y=p.top();
        p.pop();
        p.push(x-y);
        ans+=min(x,y);
    }
    if(p.top()==2){
        cout<<ans+2<<endl;
    }else{
        cout<<ans+p.top()/2<<endl;
    }
}
int main() {
    ios_base::sync_with_stdio(false);
     cin.tie(NULL); 
        ll t;cin>>t;
        while(t--){
         // cout<<fixed<<setprecision(1);
          solve();
       }  
}