409260: GYM103469 L Little LCS

A string consisting of letters 'A', 'B', 'C' is good if every two adjacent letters are different.

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

You are given two strings, $$$s$$$ and $$$t$$$, consisting of letters 'A', 'B', 'C' and question marks ('?'). Find the number of ways to replace each '?' with one of 'A', 'B', 'C', so that the pair ($$$s$$$, $$$t$$$) is awesome, 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$$$ consisting of characters 'A', 'B', 'C', '?'.

The third line contains a string $$$t$$$ of length $$$2n+1$$$ consisting of characters 'A', 'B', 'C', '?'.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^6$$$.

For each test case, output the number of ways to replace each '?' with one of 'A', 'B', 'C' so that the pair $$$(s, t)$$$ is awesome, modulo $$$998\,244\,353$$$.

5
1
ABA
CBC
1
A?A
C?C
1
???
???
2
AA???
????B
3
?A?B?A?
???????

1
3
24
0
2

In the first test case, pair $$$(\texttt{ABA}, \texttt{CBC})$$$ is awesome.

In the second test case, there are $$$3$$$ ways to replace question marks to get an awesome pair: $$$(\texttt{ABA}, \texttt{CBC})$$$, $$$(\texttt{ACA}, \texttt{CBC})$$$, $$$(\texttt{ABA}, \texttt{CAC})$$$.