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

Input

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

Output

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

Note

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"