//#include<bits/stdc++.h>
//using namespace std;
//
//void solve(){
//     int n;cin>>n;
//     vector<int>vis(n+1,0);
//     string tmp;cin>>tmp;
//     string s="0"+tmp;
//     s=s+"0";
//     int ans=0;
//     for(int i=1;i<=n;i++){
//         if(s[i]=='0'){
//             int l=max(0,i-1),r=min(n+1,i+1),f=0;//rr判断是否最后一个1在n位置
//             int ans_l=0,ans_r=0,fff=0;
//             while(s[l]=='1' || s[r]=='1'){
//                 if(r>=n){f=1;}
//                 if(s[l]=='1'&&vis[l]==0){ans_l++;vis[l]=1;}
//                 if(s[r]=='1'&&vis[r]==0){ans_r++;fff=1;vis[r]=1;}
//                 if(l-1>=0){l--;}
//                 if(r+1<=n+1){r++;}
//             }
//             if(fff){i=r-1;}
//             if(!f){ans+=(ans_l+ans_r);}
//             else{
//                 int ans_l2=0;
//                 for(int j=i-1;s[j]=='1';j--){
//                     ans_l2++;
//                 }
//                 ans+=(ans_l2*2+ans_r);
//             }
//         }
//     }
//     cout<<ans<<endl;
//}
//
//signed main()
//{
//    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
//    int t;cin>>t;
//    while(t--){
//        solve();


//    }
//    return 0;
//}


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

void solve() {
    int n;
    cin>>n;
    string s;
    cin>>s;
    int l,r;
    l=0;
    r=0;
    int ans=0;
    for(int i=0;i<n;i++)
    {
        if(s[i]=='1')
        {
            ans++;
            l++;
        }
        else
        {
            r=l;
            l=0;
        }
    }
    if(l>0)
    {
        ans-=l+r;
        if(l>=r)
        {
            ans+=r*2+l;
        }
        else
        {
            ans+=l*2+r;
        }
    }
    cout<<ans<<'\n';
}
signed main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t;cin>>t;
    while(t--){
        solve();
    }
    return 0;
}