#include<bits/stdc++.h>
#define endl "\n"
#define int long long
#define lowbit(x) (x & -x)
using namespace std;
const int N = 1e5 + 10, M = 1e5 + 10, inf = 0x3f3f3f3f;
typedef long long ll;
typedef pair<int, int> pii;
const ll INF = 0x3f3f3f3f3f3f3f3f;
int tr[N];
string c;
int n;
void add(int x,int v){
    for(int i=x;i<=n;i+= lowbit(i)) tr[i]+=v;
}
void solve() {
    cin>>n;
    for(int i=1;i<=n;i++) tr[i]=0;
    cin>>c;
    c=' '+c;
    int ans=0;
    for(int i=0;i<20;i++){
        for(int j=(1<<i);j<=n;j+=(1<<i+1)){
            if(tr[j]==0 && c[j]!='0'){
                add(j,1);
                ans++;
            }else if(tr[j]!=0 && c[j]=='0'){
                add(j,-tr[j]);
                ans++;
            }
        }
    }
    cout<<ans<<endl;
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
     cin >> t;
    for(int i = 1; i <= t; i ++ ) {
        solve();
    }


}