#include <bits/stdc++.h>

using namespace std;

void solve() {
	int n;
	cin >> n;
	vector<int> s1(n), s2(n);
	vector<int> t1(n), t2(n);
	string tmp;
	cin >> tmp;
	for (int i = 0; i < n; ++i) s1[i] = tmp[i] == '1';
	cin >> tmp;
	for (int i = 0; i < n; ++i) s2[i] = tmp[i] == '1';
	cin >> tmp;
	for (int i = 0; i < n; ++i) t1[i] = tmp[i] == '1';
	cin >> tmp;
	for (int i = 0; i < n; ++i) t2[i] = tmp[i] == '1';
	vector<int> c1(n), c2(n); // number of zeros
	c1[0] = s1[0] == 0;
	c2[0] = s2[0] == 0;
	for (int i = 1; i < n; ++i) {
		c1[i] = c1[i - 1] + (s1[i] == 0);
		c2[i] = c2[i - 1] + (s2[i] == 0);
	}
	auto getSum = [&](const vector<int> &ck, int l, int r) {
		if (l > r) return 0;
		return ck[r] - (l ? ck[l - 1] : 0);
	};
	vector<int> p1(n, -1), p2(n, -1); // previous banned pos
	int pre1 = -1, pre2 = -1;
	for (int i = 0; i < n; ++i) {
		if (t1[i] == 0) p1[i] = pre1, pre1 = i;
		if (t2[i] == 0) p2[i] = pre2, pre2 = i;
	}
	if (n <= 10) {
		int ans = 0;
		for (int s = 0; s < (1 << n); ++s) {
			for (int t = 0; t < (1 << n); ++t) {
				bool ok = true;
				for (int i = 0; i < n; ++i) {
					if (t1[i] == 0) {
						int l = p1[i] + 1;
						int r = i - 1;
						if (r >= 0 && getSum(c1, l, r) != (r - l + 1) - __builtin_popcount((((1 << (r + 1)) - 1) ^ ((1 << l) - 1)) & s)) {
							ok = false;
							break;
						}
						if (s1[i] != (s >> i & 1)) {
							ok = false;
							break;
						}
					}
					if (t2[i] == 0) {
						int l = p2[i] + 1;
						int r = i - 1;
						if (r >= 0 && getSum(c2, l, r) != (r - l + 1) - __builtin_popcount((((1 << (r + 1)) - 1) ^ ((1 << l) - 1)) & t)) {
							ok = false;
							break;
						}
						if (s2[i] != (t >> i & 1)) {
							ok = false;
							break;
						}
					}
				}
				if (__builtin_popcount(s) != n - c1.back() || __builtin_popcount(t) != n - c2.back()) {
					ok = false;
				}
				if (ok) {
					ans = max(ans, n - __builtin_popcount(s ^ t));
				}
			}
		}
		cout << ans << '\n';
		return;
	} else if (c1.back() == 0 || c1.back() == n) {
		int ans = 0;
		for (int i = 0; i < n; ++i) {
			if (s1[i] == s2[i]) ++ans;
		}
		cout << ans << '\n';
	} else if (c1.back() == 1 && c2.back() == 1) {
		vector<int> par(n * 2);
		iota(par.begin(), par.end(), 0);
		function<int(int)> find = [&](int x) -> int {
			return par[x] == x ? x : par[x] = find(par[x]);
		};
		for (int i = 0; i < n - 1; ++i) {
			if (t1[i] && t1[i + 1]) par[find(i + 1)] = find(i);
			if (t2[i] && t2[i + 1]) par[find(i + 1 + n)] = find(i + n);
			if (t1[i] && t2[i]) par[find(i)] = find(i + n);
		}
		if (t1[n - 1] && t2[n - 1]) par[find(n - 1)] = find(n + n - 1);
		int pos1 = -1, pos2 = -1;
		for (int i = 0; i < n; ++i) {
			if (s1[i] == 0) pos1 = i;
			if (s2[i] == 0) pos2 = i;
		}
		if (find(pos1) == find(pos2 + n)) {
			cout << n << '\n';
		} else {
			if (!t1[pos1] && !t2[pos2]) {
				cout << n - (pos1 != pos2) << '\n';
			} else if (!t1[pos1]) {
				cout << n - (find(pos1 + n) != find(pos2 + n)) << '\n';
			} else if (!t2[pos2]) {
				cout << n - (find(pos1) != find(pos2)) << '\n';
			} else {
				cout << n - 1 << '\n';
			}
		}
	} else {
		int ans = 0;
		for (int i = 0; i <= n; ++i) {
			if (i == n || t1[i] == 0) {
				int l = i == n ? pre1 + 1 : p1[i] + 1;
				int r = i - 1;
				if (r >= l) {
					ans += min(getSum(c1, l, r), getSum(c2, l, r));
					ans += min(r - l + 1 - getSum(c1, l, r), r - l + 1 - getSum(c2, l, r));
				}
				if (i != n) ans += s1[i] == s2[i];
			}
		}
		cout << ans << '\n';
	}
}

int main() {
	freopen("edit.in", "r", stdin);
	freopen("edit.out", "w", stdout);
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int T;
	cin >> T;
	while (0 && T--) solve();
}