#include <bits/stdc++.h>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int t;
    cin>>t;
    while(t--)
    {
        int n; cin>>n;
        string s; cin>>s;
        int rez=0;
        for(int i=0; i<n; i++)
        {
            if(s[i]=='1' and i%2==0){rez++; continue;}
            int st=((i+1)&(-i-1))/2; int pos=i-st;
            if(st==2 and s[i]!=s[i-2]){rez++; continue;}
            if(s[i]=='0')continue;
            bool ch=false;
            while(pos<i)
            {
                if(s[pos]=='1'){ch=true; break;}
                pos+=st/2; st/=2;
            }
            if(!ch)rez++;
        }
        cout<<rez<<"\n";
    }
    return 0;
}