#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<map>
using namespace std;

const int N = 1e5+10;
#define ll long long
int T;
int n;
char s[N];
int s1[N], s2[N], t1[N], t2[N], sum1[N], sum2[N], nxt1[N], nxt2[N];

int a[N], b[N]; int ans;

void dfs2(int x, int sum) {
	if(x == n+1) {
		if(sum != sum2[n]) return;
		
		int res = 0;
		for(int i = 1; i <= n; i++) res += (a[i]==b[i]);
		ans = max(ans,res);
		return;
	}
	if(t2[x] == 0 && sum != sum2[x-1]) return;
	if(t2[x] == 0) {
		b[x] = s2[x];
		dfs2(x+1,sum+s2[x]);
	}
	else {
		b[x] = 1;
		dfs2(x+1,sum+1);
		b[x] = 0;
		dfs2(x+1,sum);
	}
} 

void dfs1(int x, int sum) {
	if(x == n+1) {
		if(sum == sum1[n]) dfs2(1,0);
		return;
	}
	if(t1[x] == 0 && sum != sum1[x-1]) return;
	if(t1[x] == 0) {
		a[x] = s1[x];
		dfs1(x+1,sum+s1[x]);
	}
	else {
		a[x] = 1;
		dfs1(x+1,sum+1);
		a[x] = 0;
		dfs1(x+1,sum);
	}
	
}

void solve() {
	ans = -1;
	dfs1(1,0);
	printf("%d\n",ans);
	return;
}

int main() {
	freopen("edit.in","r",stdin); 
	freopen("edit.out","w",stdout);
	scanf("%d",&T);
	
	while(T--) {
		scanf("%d",&n);
		scanf(" %s",s+1); for(int i = 1; i <= n; i++) s1[i] = s[i]-'0', sum1[i] = sum1[i-1]+s1[i];
		scanf(" %s",s+1); for(int i = 1; i <= n; i++) s2[i] = s[i]-'0', sum2[i] = sum2[i-1]+s2[i];
		scanf(" %s",s+1); for(int i = 1; i <= n; i++) t1[i] = s[i]-'0';
		scanf(" %s",s+1); for(int i = 1; i <= n; i++) t2[i] = s[i]-'0';
		int temp = n+1;
		nxt1[n+1] = nxt2[n+1] = n+2;
		for(int i = n; i >= 1; i--) {
			nxt1[i] = temp;
			if(!t1[i]) temp = i;
		}
		temp = n+1;
		for(int i = n; i >= 1; i--) {
			nxt2[i] = temp;
			if(!t2[i]) temp = i;
		}
		
		if(n <= 10) {
			solve();
			continue;
		}
		
		bool f1 = 1;
		for(int i = 2; i <= n; i++) {
			if(s1[i] != s1[i-1]) f1 = 0;
		}
		if(f1) {
			int ans = 0;
			if(s1[1] == 1) ans = sum2[n];
			else ans = n-sum2[n];
			printf("%d\n",ans);
			continue;
		}
		
		bool f2 = 1;
		for(int i = 1; i <= n; i++) {
			if(t1[i] != t2[i]) f2 = 0;
		}
		if(f2) {
			int ans = 0, lst = 0; int len, si, sj;
			for(int i = 1; i <= n; i++) {
				if(t1[i] == 0) {
					ans += (s1[i]==s2[i]);
					len = i-1-lst, si = sum1[i-1]-sum1[lst], sj = sum2[i-1]-sum2[lst];
					ans += min(si,sj)+min(len-si,len-sj);
					lst = i;
				}
			}
			len = n-lst, si = sum1[n]-sum1[lst], sj = sum2[n]-sum2[lst];
			ans += min(si,sj)+min(len-si,len-sj);
			printf("%d\n",ans);
			continue;
		}
		
		int temp1 = 0, temp2 = 0;
		for(int i = 1; i <= n; i++) temp1 += t1[i], temp2 += t2[i];
		if(temp1 == temp2 && temp1 == n-1) {
			int x, y;
			for(int i = 1; i <= n; i++) if(t1[i] == 0) {
				x = i; break;
			}
			for(int i = 1; i <= n; i++) if(t2[i] == 0) {
				y = i; break;
			}
			int ans = 0;
			if(x == y) {
				ans += (s1[x]==s2[x]);
				int len, si, sj;
				len = x-1, si = sum1[x-1], sj = sum2[x-1];
				ans += min(si,sj)+min(len-si,len-sj);
				len = n-x, si = sum1[n]-sum1[x], sj = sum2[n]-sum2[x];
				ans += min(si,sj)+min(len-si,len-sj);
				printf("%d\n",ans);
				continue;
			}
			if(x > y) {
				for(int i = 1; i <= n; i++) swap(s1[i],s2[i]), swap(t1[i],t2[i]), swap(sum1[i],sum2[i]);
				swap(x,y);
			}
			int len, si, sj, resi, resj;
			len = x, si = sum1[x], sj = sum2[x];			
			ans += min(si,sj)+min(len-si,len-sj); resj = max(0,sum2[y-1]-si);
			len = n-y+1, si = sum1[n]-sum1[y-1], sj = sum2[n]-sum2[y-1];
			ans += min(si,sj)+min(len-si,len-sj); resi = max(0,sum1[n]-sum1[x]-sj);
			if(x != y-1) {
				len = y-x-1;
				ans += min(resi,resj)+min(len-resi,len-resj);
			}
			printf("%d\n",ans);
			continue;
		} 
		
		printf("%d\n",min(sum1[n],sum2[n])+min(n-sum1[n],n-sum2[n]));

	}
	
	return 0;
}
