#include <iostream>
#include <cstdio>
#include <algorithm>
#define ll int
using namespace std;
const ll N=1e5+10;
ll T,n;
string s1,s2,t1,t2;
inline ll lowbit(ll x){return x&(-x);}
inline ll popct(ll x){
	ll ret=0;
	while(x){x-=lowbit(x);ret++;}
	return ret;
}
void solvemin(){
	ll mx=(1<<n),cnts1=0,cnts2=0,ans=-1;
	for(ll i=1;i<=n;i++){
		cnts1+=(s1[i]=='1');
		cnts2+=(s2[i]=='1');
	}
	for(ll i=0;i<mx;i++){
		if(popct(i)!=cnts1) continue;
		ll o1=0,oi=0;
		bool flag=1;
		for(ll j=1;j<=n;j++){
			if(t1[j]=='0'){
				if(((i>>(j-1))&1)!=s1[j]-'0'||o1!=oi){
					flag=0;
					break;
				}
				o1=oi=0;
			}
			else{
				o1+=(s1[j]=='1');
				oi+=((i>>(j-1)&1));
			}
		}
		if(o1!=oi) flag=0;
		if(!flag) continue;
		for(ll k=0;k<mx;k++){
			if(popct(k)!=cnts2) continue;
			o1=oi=0;
			flag=1;
			for(ll j=1;j<=n;j++){
				if(t2[j]=='0'){
					if(((k>>(j-1))&1)!=s2[j]-'0'||o1!=oi){
						flag=0;
						break;
					}
					o1=oi=0;
				}
				else{
					o1+=(s2[j]=='1');
					oi+=((k>>(j-1)&1));
				}
			}
			if(o1!=oi) flag=0;
			if(!flag) continue;
			ll nans=0;
			for(ll ps=0;ps<n;ps++) nans+=(((i>>ps)&1)==((k>>ps)&1));
			ans=max(ans,nans);
		} 
	}
	cout<<ans<<"\n";
}
void solveB(){
	ll s10=0,s11=0,s20=0,s21=0,ans=0;
	for(ll i=1;i<=n;i++){
		if(t1[i]=='0'){
			ans+=min(s10,s20)+min(s11,s21);
			ans+=(s1[i]==s2[i]);
			s10=s11=s20=s21=0;
		}
		else{
			s10+=(s1[i]=='0');s20+=(s2[i]=='0');
			s11+=(s1[i]=='1');s21+=(s2[i]=='1');
		}
	}
	ans+=min(s10,s20)+min(s11,s21);
	cout<<ans<<"\n";
}
ll nxts1[N],nxts2[N];
void solve(){
	cin>>n>>s1>>s2>>t1>>t2;
	s1=' '+s1,s2=' '+s2,t1=' '+t1,t2=' '+t2;
	if(n<=10){
		solvemin();
		return;
	}
	bool A=1;
	ll ans=0;
	for(ll i=1;i<=n;i++){
		ans+=(s1[i]==s2[i]);
		if(i>1&&s1[i]!=s1[i-1]) A=0;
	}
	if(A){
		cout<<ans<<"\n";
		return;
	}
	if(t1==t2){
		solveB();
		return;
	}
	ans=0;
	ll s10=0,s11=0,s20=0,s21=0,s1pos=0,s2pos=0;
	t1=t1+'0';t2=t2+'0';
	s1=s1+'1';s2=s2+'0';
	nxts1[n+1]=nxts2[n+1]=n+1;
	for(ll i=n;i>=1;i--){
		nxts1[i]=nxts1[i+1];
		nxts2[i]=nxts2[i+1];
		if(t1[i]=='0') nxts1[i]=i;
		if(t2[i]=='0') nxts2[i]=i;
	}
	s1pos=nxts1[1],s2pos=nxts2[1];
	for(ll i=1;i<s1pos;i++){
		s10+=(s1[i]=='0');
		s11+=(s1[i]=='1');
	}
	for(ll i=1;i<s2pos;i++){
		s20+=(s2[i]=='0');
		s21+=(s2[i]=='1'); 
	}
	while(s1pos!=n+1||s2pos!=n+1){
		ll ns1=s1pos,ns2=s2pos;
		if(s1pos==s2pos){
			ans+=min(s10,s20)+min(s11,s21)+(s1[s1pos]==s2[s2pos]);
			s10=s11=s20=s21=0;
			s1pos=nxts1[s1pos+1];
			for(ll i=ns1+1;i<s1pos;i++){
				s10+=(s1[i]=='0');
				s11+=(s1[i]=='1');
			}
			s2pos=nxts2[s2pos+1];
			for(ll i=ns2+1;i<s2pos;i++){
				s20+=(s2[i]=='0');
				s21+=(s2[i]=='1'); 
			}
		}
		else{
			if(s1pos<s2pos){
				s10+=(s1[s1pos]=='0');
				s11+=(s1[s1pos]=='1');
				ans+=min(s10,s20)+min(s11,s21);
				if(s20<s10) s21-=s10-s20,s20=0;
				else s20-=s10;
				if(s21<s11) s20-=s11-s21,s21=0;
				else s21-=s11;
				s10=s11=0;
				s1pos=nxts1[s1pos+1];
				for(ll i=ns1+1;i<s1pos;i++){
					s10+=(s1[i]=='0');
					s11+=(s1[i]=='1');
				}
			}
			else{
				s20+=(s2[s2pos]=='0');
				s21+=(s2[s2pos]=='1');
				ans+=min(s10,s20)+min(s11,s21);
				if(s10<s20) s11-=s20-s10,s10=0;
				else s10-=s20;
				if(s11<s21) s10-=s21-s11,s11=0;
				else s11-=s21;
				s20=s21=0;
				s2pos=nxts2[s2pos+1];
				for(ll i=ns2+1;i<s2pos;i++){
					s20+=(s2[i]=='0');
					s21+=(s2[i]=='1'); 
				}
			}
		}
	}
	ans+=min(s10,s20)+min(s11,s21);
	cout<<ans<<"\n";
}
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--) solve(); 
	return 0;
}