#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int l[N],r[N],L[N],R[N];
int suma[N],sum[N],sumb[N],summ[N];
int T,n,cnta=0,cntb=0,vis[5000];
string s1,s2,s3,s4,s,ss[N],S[N];

inline int hsh(){
    int res=0;
    for(int i=1; i<=n; i++){
        if(s[i]=='1') res+=(1<<i); 
    }
    return res;
}

inline void dfs(int x){
    for(int i=1; i<=n; i++){
        if(s3[i]=='0') continue;
        for(int j=i+1; j<=n; j++){
            if(s3[j]=='0') break;
            swap(s[i],s[j]);
            int p=hsh();
            if(!vis[p]){
               vis[p]=1,cnta++;
               for(int k=0; k<=n; k++)  ss[cnta][k]=s[k];
               dfs(x+1); 
            }
            swap(s[i],s[j]);
        }
    }
}
inline void Dfs(int x){
    for(int i=1; i<=n; i++){
        if(s4[i]=='0') continue;
        for(int j=i+1; j<=n; j++){
            if(s4[j]=='0') break;
            swap(s[i],s[j]);
            int p=hsh();
            if(!vis[p]){
               vis[p]=1,cntb++;
               for(int k=0; k<=n; k++) S[cntb][k]=s[k];
               Dfs(x+1); 
            }
            swap(s[i],s[j]);
        }
    }
}
inline int comp(int x, int y){
    int res=0;
    for(int k=1; k<=n; k++){
        if(ss[x][k]==S[y][k]) res++;
    }
    return res;
}

int main(){
    freopen("edit.in","r",stdin);
    freopen("edit.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>T;
    while(T--){
        cin>>n;
        cin>>s1>>s2>>s3>>s4;
        s1=' '+s1,s2=' '+s2,s3=' '+s3,s4=' '+s4;
        if(n<=10){
            memset(vis,0,sizeof(vis));
            cnta=cntb=0;
            for(int i=0; i<=n; i++) s[i]=s1[i];
            vis[hsh()]=1,cnta++;
            for(int i=1; i<=n; i++) ss[cnta][i]=s[i];
            dfs(0);
            memset(vis,0,sizeof(vis));
            for(int i=1; i<=n; i++) s[i]=s2[i];
            vis[hsh()]=1,cntb++;
            for(int i=1; i<=n; i++) S[cntb][i]=s[i];
            Dfs(0);
            //cout<<cnta<<' '<<cntb<<'\n';
            int ans=0;
            for(int i=1; i<=cnta; i++){
                for(int j=1; j<=cntb; j++){
                    ans=max(ans,comp(i,j));
                }
            }
            cout<<ans<<'\n';
            continue;
        }
        bool fg=true,flag=true;
        for(int i=2; i<=n; i++){
            if(s1[i]!=s1[i-1]) fg=false;
            if(s3[i]!=s4[i]) flag=false;
        }
        if(fg){
            int ans=0;
            for(int i=1; i<=n; i++){
                if(s1[i]==s2[i]) ans++;
            }
            cout<<ans<<'\n';
            continue;
        }
        if(flag){
            int ans=0,ep=-1,tot=0;
            for(int i=1; i<=n; i++){
                if(s3[i]=='0'){
                    if(ep==1) ep=-1,r[tot]=i-1;
                }else{
                    if(ep==-1) ep=1,l[++tot]=i;
                }
            }
            if(s3[n]=='1') r[tot]=n;
            int i=1,tmp=1;
            while(i<=n){
                if(i<l[tmp]) ans+=(s1[i]==s2[i]);
                if(i==l[tmp]){
                    int x=0,y=0,xx=0,yy=0;
                    for(int j=l[tmp]; j<=r[tmp]; j++){
                        if(s1[j]=='1') x++;
                        else y++;
                        if(s2[j]=='1') xx++;
                        else yy++;
                    }
                    //cout<<x<<' '<<xx<<' '<<y<<' '<<yy<<'\n';
                    ans+=min(x,xx)+min(y,yy);
                    //cout<<ans<<'\n';
                    i=r[tmp],tmp++;
                }
                i++;
            }
            cout<<ans<<'\n';
            continue;
        }
        int ep=-1,tot=0,Tot=0;
        int c=0,d=0;
        for(int i=1; i<=n; i++){
            if(s3[i]=='0'){
                c++;
                if(ep==1) ep=-1,r[tot]=i-1;
            }else{
                if(ep==-1) ep=1,l[++tot]=i;
            }
        }
        if(s3[n]=='1') r[tot]=n;
        ep=-1;
        for(int i=1; i<=n; i++){
            if(s4[i]=='0'){
                d++;
                if(ep==1) ep=-1,R[Tot]=i-1;
            }else{
                if(ep==-1) ep=1,L[++Tot]=i;
            }
        }    
        if(s4[n]=='1') R[Tot]=n;
        cout<<n<<'\n'; 
    }
    return 0;
}
