Little L has a directed graph where the vertices are divided into $k$ layers. The $i$-th layer has $n_i$ vertices. The number of vertices in the first layer is equal to the number of vertices in the $k$-th layer, i.e., $n_1 = n_k$, and for each layer $j$ ($2 \le j \le k - 1$), $n_1 \le n_j \le 2n_1$. For vertices in layer $j$ ($1 \le j < k$), edges starting from them only connect to vertices in layer $j + 1$. There are no edges pointing to vertices in the first layer, and vertices in the $k$-th layer do not have edges pointing to any other vertices.

Little L wants to select $n_1$ paths from this graph, where each path starts at a vertex in the first layer and ends at a vertex in the $k$-th layer, such that every vertex in the graph appears in at most one path. More specifically, if we label the vertices in each layer as $1, 2, \dots, n_i$, then each path can be written as a $k$-tuple $(p_1, p_2, \dots, p_k)$, representing that the path passes through vertex $p_j$ in layer $j$ ($1 \le p_j \le n_j$) in sequence, and there is an edge from vertex $p_j$ in layer $j$ to vertex $p_{j+1}$ in layer $j+1$ for all $1 \le j < k$.

Little L draws these paths on paper and finds that they produce several intersection points. For two paths $P$ and $Q$, let their edges between layer $j$ and layer $j+1$ be $(P_j, P_{j+1})$ and $(Q_j, Q_{j+1})$ respectively. If $$(P_j - Q_j) \times (P_{j+1} - Q_{j+1}) < 0$$ then we say they produce an intersection point after layer $j$. The number of intersection points for two paths is the total number of intersection points produced after layers $1, 2, \dots, k-1$. For a complete set of paths, the total number of intersection points is the sum of the intersection points between every pair of distinct paths. The figure below shows an example of 3 paths with a total of 3 intersection points, where the red dots are the intersection points.

Figure 1: Example of 3 intersection points

Little L now wants to know how many more path schemes have an even number of intersection points than those with an odd number of intersection points. Two path schemes are considered identical if and only if the $k$-tuples of their $n_1$ paths, when written in the order of their starting vertex indices in the first layer, are identical. Since the final result may be very large, please output the value modulo 998244353 (a large prime).

The input contains multiple test cases. The first line contains a positive integer $T$, representing the number of test cases. For each test case:

The first line contains a positive integer $k$, representing the total number of layers.

The second line contains $k$ integers $n_1, n_2, \dots, n_k$, representing the number of vertices in each layer. It is guaranteed that $n_1 = n_k$ and $n_1 \le n_i \le 2n_1$ for $2 \le i \le k - 1$.

The third line contains $k - 1$ integers $m_1, m_2, \dots, m_{k-1}$, representing the number of edges from layer $j$ to layer $j+1$ for $1 \le j < k$. It is guaranteed that $m_j \le n_j \times n_{j+1}$.

The next $k - 1$ sections of input each contain $m_j$ lines, where each line contains two integers $u, v$, representing an edge from vertex $u$ in layer $j$ to vertex $v$ in layer $j+1$.

The data guarantees that there are no multiple edges between the same pair of vertices.

Output $T$ lines, each containing an integer representing the answer for that test case modulo 998244353.

Examples

Input 1

1
3
2 3 2
4 4
1 1
1 2
2 1
2 3
1 2
2 1
3 1
3 2

Output 1

1

Note

The number of schemes with an even number of intersection points is 2, and the number of schemes with an odd number of intersection points is 1, so the answer is 1. Swapping the schemes of path 1 and path 2 results in the same scheme. For example, the scheme where path 1 is $(2, 3, 1)$ and path 2 is $(1, 1, 2)$ is the same as scheme 1, so it is not counted in the answer.

Input 2

(See xpath/xpath2.in in the contestant directory)

Output 2

(See xpath/xpath2.ans in the contestant directory)

Note

The constraints for this example are consistent with test cases 7–8.

Input 3

(See xpath/xpath3.in in the contestant directory)

Output 3

(See xpath/xpath3.ans in the contestant directory)

Note

The constraints for this example are consistent with test cases 9–10.

Input 4

(See xpath/xpath4.in in the contestant directory)

Output 4

(See xpath/xpath4.ans in the contestant directory)

Note

The constraints for this example are consistent with test cases 14–15.