Flexible String Revisit

Description:

Input:

The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^5$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 10^6$$$) — the length of the strings.

The second line of each test case contains the binary string $$$a$$$ of length $$$n$$$.

The third line of each test case contains the binary string $$$b$$$ of length $$$n$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^6$$$.

Output:

For each test case, output a single line containing the expected number of moves modulo $$$998\,244\,353$$$.

Formally, let $$$M = 998\,244\,353$$$. It can be shown that the answer can be expressed as an irreducible fraction $$$\frac{p}{q}$$$, where $$$p$$$ and $$$q$$$ are integers and $$$q \not \equiv 0 \pmod{M}$$$. Output the integer equal to $$$p \cdot q^{-1} \bmod M$$$. In other words, output such an integer $$$x$$$ that $$$0 \le x < M$$$ and $$$x \cdot q \equiv p \pmod{M}$$$.

Sample Input:

4
1
0
1
2
00
00
4
1000
1110
5
01001
10111

Sample Output:

1
0
665496254
665496277

Note:

In the first test case, index $$$1$$$ is chosen randomly and $$$a_1$$$ is flipped. After the move, the strings $$$a$$$ and $$$b$$$ are equal. The expected number of moves is $$$1$$$.

The strings $$$a$$$ and $$$b$$$ are already equal in the second test case. So, the expected number of moves is $$$0$$$.

The expected number of moves for the third and fourth test cases are $$$\frac{56}{3}$$$ and $$$\frac{125}{3}$$$ respectively.