시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB95555.556%

문제

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$.

예제 입력 1

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

예제 출력 1

1
3
24
0
2

힌트

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

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