如果一个由字母 ‘A’、‘B’、‘C’ 组成的字符串中，任意两个相邻的字母都不相同，则称该字符串是“好的”（good）。

如果一对长度均为 $2n + 1$ 的“好的”字符串 $(s, t)$ 的最长公共子序列长度恰好为 $n$，则称该字符串对是“极好的”（awesome）。

给定两个由字母 ‘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$，由字符 ‘A’、‘B’、‘C’、‘?’ 组成。

第三行包含一个长度为 $2n + 1$ 的字符串 $t$，由字符 ‘A’、‘B’、‘C’、‘?’ 组成。

保证所有测试用例的 $n$ 之和不超过 $10^6$。

输出格式

对于每个测试用例，输出将每个 ‘?’ 替换为 ‘A’、‘B’、‘C’ 中的一个，使得字符串对 $(s, t)$ 成为“极好的”方案数，结果对 $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

说明

在第一个测试用例中，字符串对 (ABA, CBC) 是“极好的”。

在第二个测试用例中，有 3 种替换问号的方式可以得到“极好的”字符串对：(ABA, CBC), (ACA, CBC), (ABA, CAC)。