#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
constexpr int N=2000010,p=998244353;
char s[2][N];int n,T;
int cap[2][N][3];
int redu(int k){return k>=p?k-p:k;}
int c1(int p1,int p2,int p3){
	/*
	BABABABAB
	CACACACAC
	A:p1
	B:p2
	C:p3
	*/
	bool uc=true,dc=true;int un=1,dn=1;
	for(int i=1;i<=(n<<1)+1;i+=2)
		if(!cap[0][i][p2] || !cap[1][i][p3]) return 0;
	for(int i=2;i<=(n<<1);i+=2){
		if(!cap[0][i][p1]) uc=false;if(!cap[1][i][p1]) dc=false;
		un=redu(un*(cap[0][i][p1]+cap[0][i][p3]));
		dn=redu(dn*(cap[1][i][p1]+cap[1][i][p2]));
	}
	int ans=0;
	if(uc) ans=redu(ans+dn);
	if(dc) ans=redu(ans+un);
	if(uc && dc) ans=redu(ans+p-1);
	return ans;
}
int c2(int p1,int p2,int p3){
	static int suf[2][N];
	/*
	BABABAC
	CACACAB
	A:p1
	B:p2
	C:p3
	*/
	suf[0][n+1]=suf[1][n+1]=1;
	for(int i=n;i>=0;--i)
		suf[0][i]=suf[0][i+1]&cap[0][i<<1|1][p3],suf[1][i]=suf[1][i+1]&cap[1][i<<1|1][p2];
	int ans=0;
	for(int i=2;i<=(n<<1);i+=2)
		if(!cap[0][i][p1] || !cap[1][i][p1]) return 0;
	for(int i=0;i<n;++i){
		if(!cap[0][i<<1|1][p2] || !cap[1][i<<1|1][p3]) return ans;
		ans+=(suf[0][i+1]&suf[1][i+1]);
	}
	return ans;
}
int main(){
	scanf("%d",&T);
	while(T--){
		scanf("%d%s%s",&n,s[0]+1,s[1]+1);
		for(int i=1;i<=(n<<1)+1;++i){
			for(int j=0;j<3;++j){
				if(s[0][i]=='?' || s[0][i]-'A'==j) cap[0][i][j]=1;
				else cap[0][i][j]=0;
				if(s[1][i]=='?' || s[1][i]-'A'==j) cap[1][i][j]=1;
				else cap[1][i][j]=0;
			}
		}
		int ans=0;
		for(int i=0;i<3;++i)
			for(int j=0;j<3;++j) if(j!=i)
				for(int k=0;k<3;++k) if(k!=j && k!=i)
					ans=redu(ans+c1(i,j,k)),ans=redu(ans+c2(i,j,k));
		printf("%d\n",ans);
	}
	return 0;
}