#include<cstdio>
#include<iostream>
using namespace std;
int n,ans;
const int N=1e5+10,M=2e3+10;
char s[3][N],t[3][N];
bool bz[M][M];
int cal()
{
	bool f1=false,f2=false;
	for(int i=2;i<=n;i++)
		if(s[1][i]!=s[1][i-1])
		{
			f1=true;
			break;
		}
	if(!f1) return 1;
	for(int i=1;i<=n;i++)
		if(t[1][i]!=t[2][i])
		{
			f2=true;
			break;
		}
	if(!f2) return 2;
	else return 0;
}
int chk()
{
	int res=0;
	for(int i=1;i<=n;i++)
		if(s[1][i]==s[2][i]) res++;
	return res;
}
int count(char a[])
{
	int ss=0,p=1;
	for(int i=n;i>=1;i--)
	{
		ss+=(a[i]-'0')*p;
		p<<=1;
	}
	return ss;
}
void dfs(int s1,int s2)
{
	ans=max(ans,chk());
	for(int i=2;i<=n;i++)
		if(t[1][i-1]=='1'&&t[1][i]=='1')
		{
			swap(s[1][i-1],s[1][i]);
			int tmp=count(s[1]);
			if(!bz[tmp][s2])
			{
				bz[tmp][s2]=true;
				dfs(tmp,s2);
			}
			swap(s[1][i-1],s[1][i]);
		}
	for(int i=2;i<=n;i++)
		if(t[2][i-1]=='1'&&t[2][i]=='1')
		{
			swap(s[2][i-1],s[2][i]);
			int tmp=count(s[2]);
			if(!bz[s1][tmp])
			{
				bz[s1][tmp]=true;
				dfs(s1,tmp);
			}
			swap(s[2][i-1],s[2][i]);
		}
	return;
}
int solve()
{
	int id=cal();
	ans=0;
	if(!id)
	{
		for(int i=1;i<=M-10;i++)
			for(int j=1;j<=M-10;j++)
				bz[i][j]=false;
		int t1=count(s[1]),t2=count(s[2]);
		bz[t1][t2]=true;
		dfs(t1,t2);
		return ans;
	}
	if(id==1)
	{
		for(int i=1;i<=n;i++)
			if(s[2][i]==s[1][1]) ans++;
		return ans;
	}
	if(id==2)
	{
		int cnt11=0,cnt12=0,cnt21=0,cnt22=0;
		for(int i=1;i<=n;i++)
		{
			if(t[1][i]=='0')
			{
				ans+=(s[1][i]==s[2][i]);
				ans+=min(cnt11,cnt21)+min(cnt12,cnt22);
				cnt11=cnt12=cnt21=cnt22=0;
			} 
			else
			{
				if(s[1][i]=='1') cnt11++;
				else cnt12++;
				if(s[2][i]=='1') cnt21++;
				else cnt22++;
			}
		}
		ans+=min(cnt11,cnt21)+min(cnt12,cnt22);
		return ans;
	}
	
	return 0;
}
int main()
{
	freopen("edit.in","r",stdin);
	freopen("edit.out","w",stdout); 
	int T;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n);
		scanf("%s",s[1]+1);
		scanf("%s",s[2]+1);
		scanf("%s",t[1]+1);
		scanf("%s",t[2]+1);
		printf("%d\n",solve());
	}
	return 0;
}
