A15634. Koxia and Game

Koxia and Mahiru are playing a game with three arrays $a$ , $b$ , and $c$ of length $n$ . Each element of $a$ , $b$ and $c$ is an integer between $1$ and $n$ inclusive.

The game consists of $n$ rounds. In the $i$ -th round, they perform the following moves:

- Let $S$ be the multiset $\{a_i, b_i, c_i\}$ .
- Koxia removes one element from the multiset $S$ by her choice.
- Mahiru chooses one integer from the two remaining in the multiset $S$ .

Let $d_i$ be the integer Mahiru chose in the $i$ -th round. If $d$ is a permutation $^\dagger$ , Koxia wins. Otherwise, Mahiru wins.

Currently, only the arrays $a$ and $b$ have been chosen. As an avid supporter of Koxia, you want to choose an array $c$ such that Koxia will win. Count the number of such $c$ , modulo $998\,244\,353$ .

Note that Koxia and Mahiru both play optimally.

$^\dagger$ A permutation of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ( $2$ appears twice in the array), and $[1,3,4]$ is also not a permutation ( $n=3$ but there is $4$ in the array).

Each test consists of multiple test cases. The first line contains a single integer $t$ ( $1 \leq t \leq 2 \cdot 10^4$ ) — the number of test cases. The description of test cases follows.

The first line of each test case contains a single integer $n$ ( $1 \leq n \leq {10}^5$ ) — the size of the arrays.

The second line of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ ( $1 \leq a_i \leq n$ ).

The third line of each test case contains $n$ integers $b_1, b_2, \dots, b_n$ ( $1 \leq b_i \leq n$ ).

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

Output a single integer — the number of $c$ makes Koxia win, modulo $998\,244\,353$ .

In the first test case, there are $6$ possible arrays $c$ that make Koxia win — $[1, 2, 3]$ , $[1, 3, 2]$ , $[2, 2, 3]$ , $[2, 3, 2]$ , $[3, 2, 3]$ , $[3, 3, 2]$ .

In the second test case, it can be proved that no array $c$ makes Koxia win.