#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5+10;
int T,n,s[3][N],t[3][N];
int ans,ansa;
int s1,s2,t1,t2;
int ok1[1400],ok2[1400],num1,num2;
bool A,B=true,C;
int read()
{
	int x=0,w=1;
	char ch = getchar();
	while(ch<'0' || ch>'9')
	{
		if(ch == '-') w=-1;
		ch =  getchar();
	}
	while(ch>='0' && ch<='9')
	{
		x = x*10+ch-'0';
		ch = getchar();
	}
	return x*w;
}
void put_in()
{
	A = C = false;
	B = true;
	int cnt1=0,cnt2=0;
	ansa = 0;
	for(int i = 1;i <= n;i++)
	{
		char ch; cin>>ch;
		if(ch=='0') cnt1++;
		s[1][i] = (ch=='1');
		if(n<=10) s1 = (s1<<1ll)+(ch=='1');
	}
	if(cnt1==n || cnt1==0) A=true;
	for(int i = 1;i <= n;i++)
	{
		char ch; cin>>ch;
		s[2][i] = (ch=='1');
		if(s[2][i] == s[1][i]) ansa++;
		if(n<=10) s2 = (s2<<1ll)+(ch=='1');
	}
	cnt1=0;
	for(int i = 1;i <= n;i++)
	{
		char ch; cin>>ch;
		t[1][i] = (ch=='1')?1:0;
		if(ch=='0') cnt1++;
		if(n<=10) t1 = (t1<<1ll)+(ch=='1');
	}
	for(int i = 1;i <= n;i++)
	{
		char ch; cin>>ch;
		if(ch=='0') cnt2++;
		t[2][i] = (ch=='1')?1:0;
		if(t[2][i] != t[1][i]) B=false;
		if(n<=10) t2 = (t2<<1ll)+(ch=='1');
	}
	if(cnt1==cnt2 && cnt1==1) C=true;
}
void init()
{
	for(int sta = 0;sta < (1ll<<n);sta++)
	{
		bool mar = true;
		int cnt=0,sum=0;
		if(((sta^s1)&t1) == (sta^s1))
		{
			for(int i = 1;i <= n;i++)
			{
				if(sta&(1<<(n-i))) cnt++;
				if(s[1][i] == 1) sum++;
				if(t[1][i] == 0 || i==n)
				{
					if(cnt != sum)
					{
						mar = false;
						break;
					}
					else
					{
						cnt=sum=0;
					}
				}
			}
		}
		else mar=false;
		if(mar) ok1[++num1] = sta;
		
		mar = true;
		cnt=sum=0;
		if(((sta^s2)&t2) == (sta^s2))
		{
			for(int i = 1;i <= n;i++)
			{
				if(sta&(1ll<<(n-i))) cnt++;
				if(s[2][i] == 1ll) sum++;
				if(t[2][i] == 0ll || i==n)
				{
					if(cnt != sum)
					{
						mar = false;
						break;
					}
					else
					{
						cnt=sum=0;
					}
				}
			}
		}
		else mar = false;
		if(mar) ok2[++num2] = sta;
	}
}
int Sum(int x)
{
	int res=0;
	while(x)
	{
		if(x&1ll) res++;
		x >>= 1; 
	}
	return res;
}
signed main()
{
	freopen("edit.in","r",stdin);
	freopen("edit.out","w",stdout);
	scanf("%lld",&T);
	while(T--)
	{
		scanf("%lld",&n);
		s1 = s2 = t1 = t2 = 0;
		put_in();
		ans = 0;
		if(n <= 10)
		{
			num1 = num2 = 0;
			init();
			for(int i = 1;i <= num1;i++)
			{
				int sta1 = ok1[i];
				for(int j = 1;j <= num2;j++)
				{
					int sta2 = ok2[j];
					ans = max(ans,n-Sum(sta1^sta2));
				}
			}
			printf("%lld\n",ans);
			continue;
		}
		if(A)
		{
			printf("%lld\n",ansa);
			continue;
		}
		if(B)
		{
			int cnt1=0,cnt2=0,ansb=0,len=0;
			for(int i = 1;i <= n;i++)
			{
				len++;
				if(s[1][i]==1ll && t[1][i]!=0ll) cnt1++;
				if(s[2][i]==1ll && t[1][i]!=0ll) cnt2++;
				if(t[1][i]==0ll)
				{
					len--;
					ansb += min(cnt1,cnt2);
					ansb += min(len-cnt1,len-cnt2);
					if(s[1][i] == s[2][i]) ansb++;
					len=cnt1=cnt2=0;
				}
				else if(i == n)
				{
					ansb += min(cnt1,cnt2);
					ansb += min(len-cnt1,len-cnt2);
				}
			}
			printf("%lld\n",ansb);
			continue;
		}
	}
	
}
