A. Mad Max
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a permutation $$$a_1, a_2, \ldots, a_n$$$ of the integers $$$1$$$ through $$$n$$$. That is, each integer from $$$1$$$ to $$$n$$$ occurs exactly once in $$$a$$$. You are also given an array $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \le b_i \le n$$$), whose values may repeat.

Consider a permutation $$$p_1, p_2, \ldots, p_n$$$ of the integers $$$1$$$ through $$$n$$$, where each $$$p_i$$$ is read as a position in $$$a$$$. We call $$$p$$$ valid if, for every index $$$i$$$, the position $$$p_i$$$ lies inside some interval of $$$a$$$ whose maximum value equals $$$b_i$$$. Formally, for each $$$i$$$ ($$$1 \le i \le n$$$) there must exist an interval $$$[l_i, r_i]$$$ ($$$1 \le l_i \le r_i \le n$$$) with $$$l_i \le p_i \le r_i$$$ and $$$\max(a_{l_i}, a_{l_i + 1}, \ldots, a_{r_i}) = b_i$$$.

Count the number of valid permutations $$$p$$$. Since the answer may be large, output it modulo $$$998244353$$$.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$) — the length of the permutation.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ — a permutation of the integers $$$1$$$ through $$$n$$$.

The third line contains $$$n$$$ integers $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \le b_i \le n$$$) — the elements of the array $$$b$$$.

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

Output

For each test case, print a single integer — the number of valid permutations $$$p$$$, taken modulo $$$998244353$$$.

Example
Input
4
3
2 3 1
3 2 1
3
1 3 2
1 1 2
5
3 1 2 5 4
5 5 3 5 4
3
1 2 3
3 3 3
Output
1
0
18
6
Note

In the first test case, $$$a = [2, 3, 1]$$$ and $$$b = [3, 2, 1]$$$. Exactly one permutation is valid: $$$p = [2, 1, 3]$$$. To check it, for index $$$1$$$ take the interval $$$[1, 2]$$$, which contains $$$p_1 = 2$$$ and has maximum $$$\max(a_1, a_2) = 3 = b_1$$$. For index $$$2$$$ take $$$[1, 1]$$$, which contains $$$p_2 = 1$$$ and has maximum $$$2 = b_2$$$. And for index $$$3$$$ take $$$[3, 3]$$$, which contains $$$p_3 = 3$$$ and has maximum $$$1 = b_3$$$.

In the second test case, it can be shown that no valid permutation exists. So the answer is $$$0$$$.