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:

"aaaabaaaaaba"
"aaaabbaaabba"
"aaabbaaaabba"
"aaabbbaabbba"
"abaabbbaabba"
"ababbbbabbba"
"baaabaaababa"
"baaababaaaba"
"baaabbaabbba"
"baabbabaabba"

ABBA Counting

Examples