#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <functional>

using namespace std;

const int MOD = 998244353;

long long binpow(long long n, long long p) {
	return p?binpow(n*n%MOD, p>>1)*(p&1?n:1)%MOD:1;
}

long long bininv(long long n) { return binpow(n, MOD-2); }

int hanoi(int n) {
	return (binpow(3, n) + MOD - 1) * bininv(2) % MOD;
}

tuple<int, int, int> f(vector<int>& a) {
	if (a.size() == 0) return {0, 0, 0};
	int ab = a.back();
	a.pop_back();
	long long h = hanoi(a.size());
	auto pr = f(a);
	if (ab == 0) {
		return {get<0>(pr), (get<2>(pr)+h+1)%MOD, (get<2>(pr)+1+h+h+1+h+h)%MOD};
	}
	if (ab == 2) {
		return {(get<0>(pr)+1+h+h+1+h+h)%MOD, (get<0>(pr)+h+1)%MOD, get<2>(pr)};
	}
	return {(get<2>(pr)+1+h+h)%MOD, get<1>(pr), (get<0>(pr)+1+h+h)%MOD};
}

void solve(int test_ind){
	int n;
	cin >> n;
	vector<int> a(n), b(n);
	for (int &i: a) cin >> i;
	for (int &i: a) --i;
	for (int &i: b) cin >> i;
	for (int &i: b) --i;
	while (n && a.back() == b.back()) {
		n--;
		a.pop_back();
		b.pop_back();
	}
	if (n == 0) {
		cout << 0 << endl;
		return;
	}
	int s = a.back(), e = b.back();
	a.pop_back(); b.pop_back(); --n;
	if (n == 0) {
		cout << abs(s-e) << endl;
		return;
	}

	auto prs = f(a), pre = f(b);
	// cerr << get<0>(prs) << " " << get<1>(prs) << " " << get<2>(prs) << endl;
	// cerr << get<0>(pre) << " " << get<1>(pre) << " " << get<2>(pre) << endl;
	if ((s == 0 && e == 1) || (s == 1 && e == 0)) {
		cout << (get<2>(prs) + get<2>(pre) + 1) % MOD << endl;
	} else if ((s == 2 && e == 1) || (s == 1 && e == 2)) {
		cout << (get<0>(prs) + get<0>(pre) + 1) % MOD << endl;
	} else {
		long long h = hanoi(n);
		if (s == 2) {
			cout << (get<0>(prs) + 1 + h + h + 1 + get<2>(pre)) % MOD << endl;
		} else {
			cout << (get<2>(prs) + 1 + h + h + 1 + get<0>(pre)) % MOD << endl;
		}
	}
}

int main(){
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	int t=1;
	cin >> t;
	for(int i=0;i<t;i++){
		solve(i);
	}
	return 0;
}
