E. ABBA Counting
time limit per test
3.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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.

Example
Input
6
2
a?
2
??
4
a??a
4
ab??
12
??a?b??a??ba
12
?ab???b??a??
Output
1
2
2
2
10
22
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"