#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 zc = 0, oc = 0;
            while (pwr % 2 == 0) {
                pwr >>= 1;
                j += pwr;
                if (c[j] == 0) zc++;
                else oc++;
                
            }
            if (zc == oc) continue;
            if (c[i] == 1 && oc == 0) ans++;
            else if (c[i] == 0 && oc == 1) ans++;
        }
        cout << ans << endl;
    }
}