//// 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(); } }