// #pragma GCC optimize(3,"Ofast","inline")
// #pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
#define all(v) v.begin(), v.end()
#define point(n) fixed << setprecision(n)
#define IOS                      \
    ios::sync_with_stdio(false); \
    cin.tie(0), cout.tie(0);
#define endl '\n'
#define inf 0x3f3f3f3f
typedef long long ll;
typedef pair<ll, ll> PII;
typedef pair<ll, array<ll, 2>> PIA;
const int N = 1e6 + 10,mod=1e9+7;
const ll INF = 0x3f3f3f3f3f3f3f3f;
int n, m, k;
int f[N];
ll e[N];int ans=0;
vector<int >h[N],d[N];
int p[N];   string s;
int lowbit(int x)
{
    return x&-x;
}
void dfs(int u)
{
    int cnt=0;
    for(auto g:h[u]){
        if(h[g].size()!=0)
        dfs(g);
        if(s[g]=='1'){
            cnt++;
        }
    }
    if(s[u]=='1'){
       // cout<<u<<' '<<cnt<<'\n';
       ans++;
    }else {
        //cout<<u<<' '<<cnt<<'\n';
        if(cnt==1)ans+=2;
    }
   
}
void solve()
{   
    cin >> n;
    ans=0;
    for(int i=0;i<=n;i++){
        h[i].clear();
    }
 
    cin >> s;
    s=" "+s;
    vector<int >cnt(n+1);
   for(int i=1;i<=n;i++){
        int t=lowbit(i);
        if(i+t<=n){
            cnt[i]++;
            h[i+t].push_back(i);      
           // cout<<i+t<<' '<<i<<'\n';
        }
   }
   for(int i=1;i<=n;i++){
        if(!cnt[i]){
            dfs(i);
            //cout<<ans<<'\n';
        }
   }
   cout<<ans<<'\n';
   
   

 
}
int main()
{
    IOS;
    int _ = 1;
    cin >> _;
    while (_--)
    {
        solve();
    }
    return 0;
}