Little LCS

A string made of the letters A, B, and C is good if every two adjacent letters are different.

A pair of good strings $(s, t)$ of length $2n + 1$ is awesome if the length of their longest common subsequence (LCS) is exactly $n$.

You are given two strings, $s$ and $t$, made of the letters A, B, C and question marks (?). Count the ways to replace each ? with A, B, or C so that the pair $(s, t)$ is awesome. Output the count modulo $998\,244\,353$.

The first line contains a single integer $t$ ($1 \le t \le 10^5$), the number of test cases.

The first line of each test case contains a single integer $n$ ($1 \le n \le 10^6$). The second line contains a string $s$ of length $2n+1$, and the third line contains a string $t$ of length $2n+1$. Both strings consist of A, B, C, and ?.

The sum of $n$ over all test cases does not exceed $10^6$.

For each test case, print the number of ways to replace the question marks so that $(s, t)$ is awesome, modulo $998\,244\,353$, on its own line.

In the first test case, the pair (ABA, CBC) is awesome.

In the second test case, there are 3 ways to replace the question marks so that the pair is awesome: (ABA, CBC), (ACA, CBC), and (ABA, CAC).