You are given two binary strings $a$ and $b$ of length $n$. In each move, the string $a$ is modified in the following way.

• An index $i$ ($1 \leq i \leq n$) is chosen uniformly at random. The character $a_i$ will be flipped. That is, if $a_i$ is $0$, it becomes $1$, and if $a_i$ is $1$, it becomes $0$.

What is the expected number of moves required to make both strings equal for the first time?

A binary string is a string, in which the character is either $\tt{0}$ or $\tt{1}$.

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 \lt M$ and $x \cdot q \equiv p \pmod{M}$.

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.