There is a rooted tree with $n$ nodes, where the root is node 1. Each node is occupied by a person who is either an "honest person" (always tells the truth) or a "liar" (always lies).

Now, for each $i \in [1, n]$, the person at node $i$ makes a statement: "In the subtree rooted at my node, there are exactly $a_i$ honest people."

A "truth-assignment" is an assignment of either "honest" or "liar" to the person at each node. You need to calculate the number of possible truth-assignments that satisfy the following logical consistency conditions:

• For any node $i$, if the person at that node is an honest person, then the stated number $a_i$ must be equal to the actual total number of honest people in their subtree.
• For any node $i$, if the person at that node is a liar, then the stated number $a_i$ must not be equal to the actual total number of honest people in their subtree.

gsh is very interested in the truth and wants to know the total number of truth-assignments that satisfy the above conditions. Please output the answer modulo $998244353$.

Input

The first line contains an integer $T$ ($1 \le T \le 5000$), representing the number of test cases.

For each test case: The first line contains a positive integer $n$ ($1 \le n \le 5000$, $\sum n \le 5000$), representing the number of nodes. The second line contains $n$ space-separated non-negative integers $a_i$ ($0 \le a_i \le n$). * The next $n - 1$ lines each contain two positive integers $u_i, v_i$ ($1 \le u_i, v_i \le n$), representing an edge. It is guaranteed that the input edges form a tree.

Output

For each test case, output a single integer representing the answer modulo $998244353$.

Examples

Input 1

6
3
1 2 3
1 2
1 3
3
0 2 3
1 2
1 3
3
0 2 1
1 2
1 3
5
5 1 1 1 4
5 1
4 5
5 3
2 5
5
5 1 3 4 1
5 3
2 3
1 4
4 3
6
3 5 1 0 1 0
2 6
4 5
2 3
6 1
4 2

Output 1

2
0
1
10
7
3

Note

For the first test case, there are 2 possibilities: 1. Node 1 tells the truth, node 2 lies, node 3 lies. 2. Node 1 lies, node 2 lies, node 3 lies.

For the second test case, there are no valid solutions.

For the third test case, there is only one possibility: node 1 lies, node 2 lies, node 3 tells the truth.