#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;
const int RP=1e3+10;
int s1[maxn],s2[maxn],t1[maxn],t2[maxn];
int cnt10[maxn],cnt20[maxn],cnt11[maxn],cnt21[maxn];
int p1[maxn],p2[maxn];
int num[RP];
int n;
void solve0() {
int ans=0,len=0,cntt1=0,cntt0=0,cnts1=0,cnts0=0;
for(int i=0;i<(1<<n);i++) {
int tmp=i;
len=0;
while(tmp) {
num[++len]=tmp%2;
tmp/=2;
}
len=n;
reverse(num+1,num+len+1);
bool flag=1;
cntt1=0,cntt0=0,cnts0=0,cnts1=0;
for(int i=1;i<=len;i++) {
if(!t1[i]) {
if(s1[i]!=num[i]) {
flag=0;
break;
}
if((cntt1!=cnts1)||(cnts0!=cntt0)) {
flag=0;
break;
}
cnts1=0,cnts0=0;
cntt0=0,cntt1=0;
continue;
}
cnts1+=(s1[i]==1);
cnts0+=(s1[i]==0);
cntt0+=(num[i]==0);
cntt1+=(num[i]==1);
}
if(!flag) continue;
if((cntt1!=cnts1)||(cnts0!=cntt0)) continue;
cntt1=0,cntt0=0,cnts0=0,cnts1=0;
int res=0;
for(int i=1;i<=len;i++) {
if(!t2[i]) {
res+=(num[i]==s2[i]);
res+=min(cntt1,cnts1);
res+=min(cntt0,cnts0);
cntt1=cnts1=cntt0=cnts0=0;continue;
}
cnts1+=(s2[i]==1);
cnts0+=(s2[i]==0);
cntt0+=(num[i]==0);
cntt1+=(num[i]==1);
}
res+=min(cntt1,cnts1);
res+=min(cntt0,cnts0);
ans=max(ans,res);
}
cout<<ans<<"\n";
}
void solveA() {
int ans=0;
for(int i=1;i<=n;i++) {
if(s1[i]==s2[i]) ans++;
}
cout<<ans<<"\n";
return;
}
void solveB() {
int sum11=0,sum21=0,sum10=0,sum20=0,ans=0;
for(int i=1;i<=n;i++) {
if(t1[i]==0) {
ans+=(s1[i]==s2[i]);
ans+=min(sum11,sum21);
ans+=min(sum10,sum20);
sum11=sum21=sum10=sum20=0;
continue;
}
sum11+=(s1[i]==1);
sum21+=(s2[i]==1);
sum10+=(s1[i]==0);
sum20+=(s2[i]==0);
}
ans+=min(sum11,sum21);
ans+=min(sum10,sum20);
cout<<ans<<"\n";
}
void solve() {
cin>>n;
char tmp;
int flag1=0,flag2=1;
for(int i=1;i<=n;i++) {
cin>>tmp;
s1[i]=tmp-'0';
if(i==1) flag1=s1[i];
else if(s1[i]!=flag1) {
flag1=-1;
}
}
for(int i=1;i<=n;i++) {
cin>>tmp;
s2[i]=tmp-'0';
}
for(int i=1;i<=n;i++) {
cin>>tmp; t1[i]=tmp-'0';
cnt11[i]=cnt21[i]=cnt10[i]=cnt20[i]=0;
}
for(int i=1;i<=n;i++) {
cin>>tmp; t2[i]=tmp-'0';
if(t1[i]!=t2[i]) flag2=0;
}
if(n<=10) {
solve0();
return;
}
if(flag1!=-1) {
solveA();
return;
}
if(flag2) {
solveB();
return;
}
int tot1=0,tot2=0;
for(int i=1;i<=n;i++) {
if(t1[i]==0) {
++tot1;continue;}
p1[i]=tot1;
cnt11[tot1]+=(s1[i]==1);
cnt10[tot1]+=(s1[i]==0);
}
for(int i=1;i<=n;i++) {
if(t2[i]==0) {
++tot2;continue;}
p2[i]=tot2;
cnt21[tot2]+=(s2[i]==1);
cnt20[tot2]+=(s2[i]==0);
}
int ans=0;
for(int i=1;i<=n;i++) {
if(t1[i]==0) {
int P1=p1[i-1];
int P2=p2[i];
int sum11=t2[i-1]==0?0:cnt11[P1],sum10=t2[i-1]==0?0:cnt10[P1];
int A=min(sum10,cnt20[P2]);
int B=min(sum11,cnt21[P2]);
ans=ans+A+B;
cnt20[P2]-=A;
cnt21[P2]-=B;
if(s1[i]==1) {
A=min(1,cnt21[P2]);
ans+=A;
cnt21[P2]-=A;
}
else {
A=min(1,cnt20[P2]);
ans+=A;
cnt20[P2]-=A;
}
}
if(t2[i]==0) {
int P1=p2[i-1];
int P2=p1[i];
int sum21=t1[i-1]*cnt21[P1],sum20=t1[i-1]*cnt20[P1];
int A=min(sum20,cnt10[P2]);
int B=min(sum21,cnt11[P2]);
ans=ans+A+B;
cnt10[P2]-=A;
cnt11[P2]-=B;
if(s2[i]==1) {
A=min(1,cnt11[P2]);
ans+=A;
cnt11[P2]-=A;
}
else {
A=min(1,cnt11[P2]);
ans+=A;
}
}
}
if(t1[n]&&t2[n])ans+=min(cnt10[p1[n]],cnt20[p2[n]]),
ans+=min(cnt11[p1[n]],cnt21[p2[n]]);
cout<<ans<<"\n";
}
int main() {
cin.tie(0), cout.tie(0);
ios::sync_with_stdio(0);
freopen("edit.in","r",stdin);
freopen("edit.out","w",stdout);
int T;
cin>>T;
while(T--) {
solve();
}
return 0;
}