CF2201E.ABBA Counting

You are given a string $T$ of length $n$ ($n$ is even), which consists of 'a', 'b', and '?'.

Please count the strings $S$ which satisfy the following conditions:

• $|S|=n$;
• $S_i$ is either 'a' or 'b' for all $1 \le i \le n$;
• $S_i=T_i$ for all $1 \le i \le n$ such that $T_i$ is not '?';
• There exist two (possibly empty) strings $A$ and $B$ such that $S=A+B+B+A$. Here, $+$ denotes string concatenation.

As the answer may be inexplicably huge, you are only asked to compute it modulo $998\,244\,353$.

给你一个长度为 $n$（$n$ 为偶数）的字符串 $T$，它仅由字符 'a'、'b' 和 '?' 组成。

请计算满足以下条件的字符串 $S$ 的个数：

• $|S|=n$；
• 对所有 $1 \le i \le n$，$S_i$ 为 'a' 或 'b'；
• 对所有满足 $T_i \neq\, \text{'?'}$ 的下标 $i$（$1 \le i \le n$），有 $S_i=T_i$；
• 存在两个（可能为空）字符串 $A$ 和 $B$，使得 $S=A+B+B+A$。此处 $+$ 表示字符串连接。

由于答案可能极其巨大，你只需输出其对 $998\,244\,353$ 取模的结果。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($2 \le n \le 400\,000$, $n$ is even).

The second line of each test case contains a string $T$ of length $n$, consisting of 'a', 'b', and '?'.

It is guaranteed that the sum of $n$ over all test cases does not exceed $400\,000$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$2 \le n \le 400\,000$，且 $n$ 为偶数）。

每个测试用例的第二行包含一个长度为 $n$ 的字符串 $T$，由字符 'a'、'b' 和 '?' 组成。

保证所有测试用例的 $n$ 之和不超过 $400\,000$。

For each test case, output the answer modulo $998\,244\,353$ on a separate line.

对于每个测试用例，在单独一行中输出答案对 $998\,244\,353$ 取模的结果。

For the fifth test case, there are $10$ corresponding strings which are as follows:

1. "aaaabaaaaaba"
2. "aaaabbaaabba"
3. "aaabbaaaabba"
4. "aaabbbaabbba"
5. "abaabbbaabba"
6. "ababbbbabbba"
7. "baaabaaababa"
8. "baaababaaaba"
9. "baaabbaabbba"
10. "baabbabaabba"

对于第五个测试用例，共有 $10$ 个对应的字符串，如下所示：

1. "aaaabaaaaaba"
2. "aaaabbaaabba"
3. "aaabbaaaabba"
4. "aaabbbaabbba"
5. "abaabbbaabba"
6. "ababbbbabbba"
7. "baaabaaababa"
8. "baaababaaaba"
9. "baaabbaabbba"
10. "baabbabaabba"