#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath> 
#include<queue>
#define N int(1e5+24)
#define RR register
using namespace std;//why the IDE on my computer cannot debug?!! 
inline long long read(){
	RR long long x=0,f=1;
	RR char ch=getchar();
	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
	if(ch=='-')f=-1,ch=getchar();
	while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
//	cout<<endl;
	return f*x;
}
long long n;
bool s[2][N],te[2][N],O[N];
bool k,sa;
int main(){
	freopen("edit.in","r",stdin);
	freopen("edit.out","w",stdout);
	int t=read();
	while(t--){
//		cout<<t<<endl; 
		n=read();
//		cout<<n<<endl;
		char tmp;
		sa=true;
		for(int i=0;i<n;i++){
			tmp=getchar();
			while(tmp<'0'||tmp>'9')tmp=getchar();
			if(!i)k=(tmp^48);
			if(tmp^48){
				s[0][i]=1;
				if(!k)sa=false;
			}else{
				s[0][i]=0;
				if(k)sa=false;
			}
		}
		if(sa){
			long long cnt=0;
			for(int i=0;i<n;i++){
				tmp=getchar();
				while(tmp<'0'||tmp>'9')tmp=getchar();
				if((tmp^48)==k)++cnt;
			}
			printf("%lld\n",cnt);
			int c1=0,c2=0;
			for(int i=0;i<n;i++){
				tmp=getchar();
				while(tmp<'0'||tmp>'9')tmp=getchar();
				if(tmp^48)te[0][i]=1;
				else te[0][i]=0,++c1;
			}
			for(int i=0;i<n;i++){
				tmp=getchar();
				while(tmp<'0'||tmp>'9')tmp=getchar();
				if(tmp^48)te[1][i]=1;
				else te[1][i]=0,++c2;
				O[i]=te[1][i]||te[0][i];
			}
			continue;
		}
		for(int i=0;i<n;i++){
			tmp=getchar();
			while(tmp<'0'||tmp>'9')tmp=getchar();
			if(tmp^48)s[1][i]=1;
			else s[1][i]=0;
		}
		int c1=0,c2=0;
		for(int i=0;i<n;i++){
			tmp=getchar();
			while(tmp<'0'||tmp>'9')tmp=getchar();
			if(tmp^48)te[0][i]=1;
			else te[0][i]=0,++c1;
		}
		for(int i=0;i<n;i++){
			tmp=getchar();
			while(tmp<'0'||tmp>'9')tmp=getchar();
			if(tmp^48)te[1][i]=1;
			else te[1][i]=0,++c2;
			O[i]=te[1][i]||te[0][i];
		}
//		if(c1==c2&&c1==1){
//			int k1=0,k2=0,ans=0,l=0;
//			for(int i=0;i<n;i++){
//				if(t[0][i]&&t[1][i]){
//					if(s[0][i])k1++;
//					if(s[1][i])k2++;
//				}
//				else{
//					if(s[0][i]==s[1][0])++ans;
//					int len=i-l+1;
//					ans+=len-abs(k1-k2)*2;
//					l=i+1; 
//				}
//			}
//		}
		long long ans=0;
		int k1=0,k2=0,l=0;
		for(int i=0;i<n;i++){
			if(O[i]){
				if(s[0][i])k1++;
				if(s[1][i])k2++;
			}
			else{
				if(s[0][i]==s[1][0])++ans;
				int len=i-l;
				ans+=len-abs(k1-k2);
				l=i+1; 
				k1=0,k2=0;
			}
		}
		ans+=n-l-abs(k1-k2);
		printf("%lld\n",ans);
	}
	return 0;
}
