작은 LCS

알파벳 A, B, C로만 이루어진 문자열에서 인접한 두 글자가 모두 다르면 이 문자열을 좋은 문자열이라고 한다.

길이가 $2n + 1$인 좋은 문자열 두 개 $(s, t)$의 쌍은, 두 문자열의 최장 공통 부분 수열(LCS) 길이가 정확히 $n$일 때 멋진 쌍이다.

A, B, C와 물음표(?)로 이루어진 문자열 $s$와 $t$가 주어진다. 각 ?를 A, B, C 중 하나로 바꾸어 $(s, t)$가 멋진 쌍이 되는 방법의 수를 구하라. 답은 $998\,244\,353$으로 나눈 나머지로 출력한다.

첫 줄에 테스트 케이스의 개수 $t$ ($1 \le t \le 10^5$)가 주어진다.

각 테스트 케이스의 첫 줄에는 정수 $n$ ($1 \le n \le 10^6$)이 주어진다. 둘째 줄에는 길이가 $2n+1$인 문자열 $s$가, 셋째 줄에는 길이가 $2n+1$인 문자열 $t$가 주어진다. 두 문자열은 A, B, C, ?로만 이루어진다.

모든 테스트 케이스의 $n$ 합은 $10^6$을 넘지 않는다.

각 테스트 케이스마다 ?를 채워 $(s, t)$가 멋진 쌍이 되는 방법의 수를 $998\,244\,353$으로 나눈 나머지를 한 줄에 출력한다.

첫 번째 테스트 케이스에서 쌍 (ABA, CBC)는 멋진 쌍이다.

두 번째 테스트 케이스에서 ?를 채워 멋진 쌍을 만드는 방법은 3가지이다. (ABA, CBC), (ACA, CBC), (ABA, CAC)가 그것이다.