#include <iostream>
#include <vector>
#include <string>
#include <fstream>
#include <algorithm>
#include <climits>
#include <cstdlib>
#include <cstdio>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <bitset>
#include <deque>
#include <queue>
#include <tuple>
#include <cmath>
#include <cctype>
#include <stack>
#include <cassert>
#include <iomanip>
#include <random>
#include <chrono>
using namespace std;
using ll = long long;

int n;
int c[100001];

int main() {
    freopen("L.in", "r", stdin);
    freopen("L.out", "w", stdout);

    int T; cin >> T;
    while (T--) {
        cin >> n;
        string s; cin >> s; s = " " + s;
        for (int i = 1; i <= n; i++) c[i] = s[i]-'0';
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            if (i%2 == 1) { ans += (c[i]==1); continue; }
            int pwr = i&-i;
            int j = i-pwr;
            int oc = 0;
            while (pwr % 2 == 0) {
                pwr >>= 1;
                j += pwr;
                if (c[j] == 1) oc++;
                
                // cout << "pair: " << i << " " << j << endl;
            }
            // cout << "testing: " << i << " " << zc << " " << oc << endl;
            if (c[i] == 1 && oc == 0) ans++;
            else if (c[i] == 0 && oc == 1) ans++;
        }
        cout << ans << endl;
    }
}