#include<bits/stdc++.h>
#include<cstring>
using namespace std;
using ll = long long;
const int maxn = 1e5 + 10;
char a[2][maxn],b[2][maxn];
int n;
namespace pts1_4{
	struct node{int bg,ed,cnt0,cnt1;}d[2][maxn];
	void calc(int x,int &cnt1){
		int cnt2 = 0,cnt3 = 0;b[x][n+1] = '0'; 
		for(int i = 1;i <= n + 1;i++)
			if(b[x][i] == '0' && (cnt2 || cnt3)){
				d[x][++cnt1].bg = i - cnt2 - cnt3;
				d[x][cnt1].ed = i - 1;
				d[x][cnt1].cnt0 = cnt2;
				d[x][cnt1].cnt1 = cnt3;
				cnt2 = cnt3 = 0;
			}
			else if(b[x][i] == '1'){
				if(a[x][i] == '0')++cnt2;
				else ++cnt3;
			}
	}
	int cnt1,cnt2;
	int dfs1(int x,int now,int cnt);
	int dfs2(int x,int nowd,int now,int cnt){
		if(now > d[x][nowd].ed)return dfs1(x,nowd + 1,cnt);
		int ans = 0;
		if(d[x][nowd].cnt0){
			--d[x][nowd].cnt0;
			a[x][now] = '0';
			ans = dfs2(x,nowd,now + 1,cnt);
			++d[x][nowd].cnt0;
		}
		if(d[x][nowd].cnt1){
			--d[x][nowd].cnt1;
			a[x][now] = '1';
			ans = max(ans,dfs2(x,nowd,now + 1,cnt));
			++d[x][nowd].cnt1;
		}
		return ans;
	}
	int dfs1(int x,int now,int cnt){
		if(now > cnt)
			if(!x)return dfs1(1,1,cnt2);
			else{
				int ans = 0;
				for(int i = 1;i <= n;i++)ans += a[0][i] == a[1][i];
				return ans;
			}
		else return dfs2(x,now,d[x][now].bg,cnt);
	}
	void main(){
		cnt1 = cnt2 = 0;
		calc(0,cnt1);
		calc(1,cnt2);
		printf("%d\n",dfs1(0,1,cnt1));
	}
}
int main(){
	freopen("edit.in","r",stdin);
	freopen("edit.out","w",stdout);
	int t;
	scanf("%d",&t);
	while(t--){
		scanf("%d%s%s%s%s",&n,a[0]+1,a[1]+1,b[0]+1,b[1]+1);
		if(n <= 10){
			pts1_4::main();
			continue;
		}
		bool flag = true;
		for(int i = 2;i <= n;i++)
			if(a[0][i] != a[0][1]){
				flag = false;
				break;
			}
		if(flag){
			int ans = 0;
			for(int i = 1;i <= n;i++)ans += a[1][i] == a[0][1];
			printf("%d\n",ans);
			continue;
		}
		flag = true;
		for(int i = 1;i <= n;i++)
			if(b[0][i] != b[1][i]){
				flag = false;
				break;
			}
		if(flag){
			int cnt11 = 0,cnt12 = 0,cnt21 = 0,cnt22 = 0,ans = 0;
			b[0][n+1] = '0';
			for(int i = 1;i <= n + 1;i++)
				if(b[0][i] == '1'){
					if(a[0][i] == '0')++cnt11;
					else ++cnt12;
					if(a[1][i] == '0')++cnt21;
					else ++cnt22;
				}
				else{
					ans += min(cnt11,cnt21) + min(cnt12,cnt22) + (i != n + 1 && a[0][i] == a[1][i]);
					cnt11 = cnt12 = cnt21 = cnt22 = 0;
				}
			printf("%d\n",ans);
			continue;
		}
	}
}
