#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "cp_debug.h"
#else
#define debug(...) 42
#endif
#define int long long
#define rep(i,a,b) for(int i = a; i < b; ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)x.size()

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<ll> vl;


template<typename T> void read(T &x){
    x = 0;char ch = getchar();ll f = 1;
    while(!isdigit(ch)){if(ch == '-')f*=-1;ch=getchar();}
    while(isdigit(ch)){x = x*10+ch-48;ch=getchar();}x*=f;
}
template<typename T, typename... Args> void read(T &first, Args& ... args) {
    read(first);
    read(args...);
}
template<typename T> void write(T x) {
    if(x > 9) write(x/10);
    putchar(x%10 + '0');
}

const int MOD = 998244353;
int add(int x, int y) { return x+y>=MOD?x+y-MOD:x+y; }
int sub(int x, int y) { return x-y<0?x-y+MOD:x-y; }
int mul(int x, int y) { return 1LL*x*y%MOD; }
int qpow(int x, int y) {
    int ret = 1;
    for(;y; y >>= 1, x = mul(x,x))
        if(y & 1) ret = mul(ret, x);
    return ret;
}
int inv(int x) { return qpow(x,MOD-2); }

void solve() {
    int n, ans = 0; 
    cin >> n;
    string s;
    cin >> s;
    s = "0" + s;
    for(int i = 1; i <= n; i++) {
        int c = __builtin_ctz(i);
        int nonzero = 0, p = i-1;
        debug(i);
        for(int j = 0; j < c; j++) {
            debug(p);
            if(s[p] != '0') nonzero++;
            p -= (1<<j);
        }
        if(s[i] == '1') {
            if(nonzero == 0) {
                ans++;
            }
        } else {
            if(nonzero == 1) {
                ans++;
            }
        }
    }
    cout << ans << '\n';
}

signed main() {
    ios::sync_with_stdio(false);
    int T; cin >> T;
    while(T--) solve();
    return 0;
}