// #pragma GCC optimize(3,"Ofast","inline")
// #pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
#define all(v) v.begin(), v.end()
#define point(n) fixed << setprecision(n)
#define IOS                      \
    ios::sync_with_stdio(false); \
    cin.tie(0), cout.tie(0);
#define endl '\n'
#define inf 0x3f3f3f3f
typedef long long ll;
typedef pair<ll, ll> PII;
typedef pair<ll, array<ll, 2>> PIA;
const int N = 1e6 + 10,mod=1e9+7;
const ll INF = 0x3f3f3f3f3f3f3f3f;
int n, m, k;
int f[N];
ll e[N];
void solve()
{   
    cin >> n;
    for(int i=0;i<=n;i++)e[i]=0;
    string s;
    cin >> s;
    s=" "+s;
    ll ans=0;
    for(int i=1;i<=n;i++){
        int t=s[i]-'0';
        int now=0;
        if(t==0&&e[i]!=0||t==1&&e[i]==0){
            now=t-e[i];
            int j=i;
            ans++;
            while(j<=n){
              //  cout<<j<<' ';
                e[j]+=now;
                j+=(j&-j);
            }
        }
       // for(int j=1;j<=n;j++)cout<<e[j]<<" \n"[j==n];
    }
    cout<<ans<<'\n';

 
}
int main()
{
    IOS;
    int _ = 1;
    cin >> _;
    while (_--)
    {
        solve();
    }
    return 0;
}