#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

ll const maxn{ll(1e5+5)};
ll t,n,ans;
string s1,s2,t1,t2;

void to1base(string &s){
	s=' '+s;
}

bool isCaseA(){
	for(ll i{2};i<=n;i++){
		if(s1[i]!=s1[1]){
			return false;
		}
	}
	return true;
}

void CaseA(){
	char s1C = s1[1];
	ll ans{n};
	for(ll i{1};i<=n;i++){
		if(s2[i]!=s1C){
			ans--;
		}
	}
	cout<<ans<<'\n';
}

bool isCaseB(){
	for(ll i{1};i<=n;i++){
		if(t1[i]!=t2[i])return false;
	}
	return true;
}

void CaseB(){
	ll s11{},s10{},s21{},s20{},ans{};
	for(ll i{1};i<=n;i++){
		if(t1[i]=='0'){
			if(s1[i]==s2[i])ans++;
			ans+=min(s10,s20);
			ans+=min(s11,s21);
			s11=0,s10=0,s21=0,s20=0;
			continue;
		}
		if(s1[i]=='1'){
			s11++;
		}else{
			s10++;
		}
		if(s2[i]=='1'){
			s21++;
		}else{
			s20++;
		}
	}
	ans+=min(s10,s20);
	ans+=min(s11,s21);
	cout<<ans<<'\n';
}

bool isCase0(){
	return n<=11;
}

ll num10[maxn],num11[maxn],num20[maxn],num21[maxn];

template<class T>
void filln(T*const t,T const& v){
	for(ll i{1};i<=n;i++){
		t[i]=v;
	}
}

char ds1[maxn],ds2[maxn];

void dfs(ll const& sidx,ll const& nidx,ll const& idx,ll const& num0,ll const& num1){
	if(idx>n&&sidx==1){
		dfs(2,1,1,num20[1],num21[1]);
		return ;
	}
	if(idx>n&&sidx==2){
		ll nans{};
		for(ll i{1};i<=n;i++){
			if(ds1[i]==ds2[i])nans++;
		}
		ans=max(ans,nans);
		return ;
	}
	if(sidx==1){
		if(t1[idx]=='0'){
			ds1[idx]=s1[idx];
			dfs(sidx,nidx+1,idx+1,num10[nidx+1],num11[nidx+1]);
			return;
		}
		if(num0>0){
			ds1[idx]='0';
			dfs(sidx,nidx,idx+1,num0-1,num1);
		}
		if(num1>0){
			ds1[idx]='1';
			dfs(sidx,nidx,idx+1,num0,num1-1);
		}
	}else{
		if(t2[idx]=='0'){
			ds2[idx]=s2[idx];
			dfs(sidx,nidx+1,idx+1,num20[nidx+1],num21[nidx+1]);
			return;
		}
		if(num0>0){
			ds2[idx]='0';
			dfs(sidx,nidx,idx+1,num0-1,num1);
		}
		if(num1>0){
			ds2[idx]='1';
			dfs(sidx,nidx,idx+1,num0,num1-1);
		}
	}
}

void Case0(){
	filln(num10,0ll);
	filln(num11,0ll);
	filln(num20,0ll);
	filln(num21,0ll);
	
	ll idx1{1},idx2{1};
	for(ll i{1};i<=n;i++){
		if(t1[i]=='0'){
			idx1++;
		}else{
			if(s1[i]=='0'){
				num10[idx1]++;
			}else{
				num11[idx1]++;
			}
		}
		
		if(t2[i]=='0'){
			idx2++;
		}else{
			if(s2[i]=='0'){
				num20[idx2]++;
			}else{
				num21[idx2]++;
			}
		}
	}
	ans=0;
	dfs(1,1,1,num10[1],num11[1]);
	cout<<ans<<'\n';
}

bool isCaseC(){
	ll num10{},num20{};
	for(ll i{1};i<=n;i++){
		if(t1[i]=='0'){
			num10++;
		}
		if(t2[i]=='0'){
			num20++;
		}
		if(num10>1||num20>1){
			return false;
		}
	}
	return true;
}

void CaseC(){
	ll idx1{},idx2{};
	for(ll i{1};i<=n;i++){
		if(t1[i]=='0'){
			idx1=i;
		}
		if(t2[i]=='0'){
			idx2=i;
		}
		if(idx1&&idx2){
			break;
		}
	}
	if(idx1==idx2){
		CaseB();
		return;
	}
	if(idx1>idx2){
		swap(idx1,idx2);
		swap(s1,s2);
		swap(t1,t2);
	}
	ll n1l1{},n1l0{},n1r1{},n1r0{},n2l1{},n2l0{},n2r1{},n2r0;
	for(ll i{1};i<=idx1;i++){
		if(s1[i]=='1'){
			n1l1++;
		}else{
			n1l0++;
		}
	}
	for(ll i{idx1+1};i<=n;i++){
		if(s1[i]=='1'){
			n1r1++;
		}else{
			n1r0++;
		}
	}
	for(ll i{1};i<=idx2;i++){
		if(s2[i]=='1'){
			n2l1++;
		}else{
			n2l0++;
		}
	}
	for(ll i{idx2+1};i<=n;i++){
		if(s2[i]=='1'){
			n2r1++;
		}else{
			n2r0++;
		}
	}
	ll ans{};
	ans+=min(n1l1,n2l1);
	ans+=min(n1l0,n2l0);
	n2l1-=min(n1l1,n2l1);
	n2l0-=min(n1l0,n2l0);
	
	ans+=min(n1r1,n2r1);
	ans+=min(n1r0,n2r0);
	n1r1-=min(n1r1,n2r1);
	n1r0-=min(n1r0,n2r0);
	
	ans+=min(n2l1,n1r1);
	ans+=min(n2l0,n1r0);
	cout<<ans<<'\n';
}

int main(){
	ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
	freopen("edit.in","r",stdin);
	freopen("edit.out","w",stdout);

	cin>>t;
	while(t--){
		cin>>n;
		cin>>s1>>s2>>t1>>t2;
		to1base(s1),to1base(s2),to1base(t1),to1base(t2);
		if(isCase0()){
			Case0();
		}else if(isCaseA()){
			CaseA();
		}else if(isCaseB()){
			CaseB();
		}else if(isCaseC()){
			CaseC();
		}else {
			cout<<"66647\n";
		}	
	}
	cout<<flush;
}
