#include <bits/stdc++.h>
#define int long long

using namespace std;

struct BIT {
    vector <int> tr;
    int n;

    BIT (int n_) {
        n = n_;
        tr.resize (n + 1);
    }

    int lowbit (int x) {
        return x & -x;
    }

    void add (int x, int c) {
        for (int i = x; i <= n; i += lowbit (i)) {
            tr[i] += c;
        }
    }

    int query (int x) {
        if (x <= 0) {
            return 0;
        }
        int ans = 0;
        for (int i = x; i > 0; i -= lowbit (i)) {
            ans += tr[i];
        }
        return ans;
    }

    int ask (int x) {
        return query (x) - query (x - 1);
    }
};

void solve () {
    int n;
    cin >> n;

    string s;
    cin >> s;

    s = " " + s;   

    BIT bit (n);

    int ans = 0;
    for (int i = 1; i <= n; i ++) {
        if (s[i] == '0') {
            int t = bit.tr[i];
            if (t == 1) {
                ans ++;
                bit.add (i, 1);
            }
        } else {
            int t = bit.tr[i];
            if (t == 0) {
                ans ++;
                bit.add (i, 1);
            }
            // if (t == 0) {
            //     ans ++;
            //     bit.add (i, 1);
            // } else if (t % 2 == 0) {
            //     bit.add (i, 1);
            // }
        }
        // cerr << i << " " << ans << '\n';
    }

    cout << ans << '\n';
}
 
signed main () {
	ios::sync_with_stdio (false);
    cin.tie (nullptr);
    
    int T = 1;
    cin >> T;

    while (T --) {
        solve ();
    }

 	return 0;
}