Problem Description

There is a binary tree with the root at vertex $1$, and each vertex $u$ in the tree has a weight $a_u$. You can perform the following two operations:

1. If vertex $u$ has left child $v$ and right child $w$, and its left child $v$ has a right child $x$, then you can perform a "rotation" on these four vertices. Let $a'_u=a_v, a'_w=a_u, a'_x=a_w, a'_v=a_x$, and then let $a_u=a'_u, a_v=a'_v, a_w=a'_w, a_x=a'_x$.
2. If vertex $u$ has left child $v$ and right child $w$, and its right child $w$ has a left child $x$, then you can perform a "rotation" on these four vertices. Let $a'_u=a_v, a'_w=a_u, a'_x=a_w, a'_v=a_x$, and then let $a_u=a'_u, a_v=a'_v, a_w=a'_w, a_x=a'_x$.

Find the number of different point weight arrays $a$ that can be obtained by performing a series of operations, modulo $998244353$.

Input

The input consists of multiple test cases. The first line contains a single integer $T$ ($1 \le T \le 1000$) - the number of test cases. Description of the test cases follows.

The first line of each test case contains one integer $n$ ($1 \leq n \leq 10^5$) - the number of vertices in the tree.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \leq a_i \leq n$) - the point weights.

Each of the following $n$ lines contains two integers $l_i, r_i$ ($0 \le l_i, r_i \le n$) - the left child and right child of vertex $i$. If a child does not exist, it is represented by $0$.

It's guaranteed that $\sum n \leq 10^6$.

Output

For each test case, print a single integer - the number of different point weight arrays $a$ that can be obtained by performing a series of operations, modulo $998244353$.

2
4
1 2 2 1
2 3
0 4
0 0
0 0
8
1 2 3 4 5 6 7 8
2 3
4 5
6 7
0 0
0 0
0 8
0 0
0 0

2
5040