This is the easy version of the problem. The difference between the versions is that in this version, $n \le 5000$. You can hack only if you solved all versions of this problem.

Given a tree $T$ with $n$ vertices rooted at $1$ and a sequence $a$ of length $n$, count the number of permutations$^{\text{∗}}$ $p$ of length $n$ that satisfy the following condition:

• For all $1 \le u \le n$, there are exactly $a_u$ vertices $v$ such that $v$ is an ancestor of $u$ in $T$ and $p_v \lt p_u$.

Output the answer modulo $998\,244\,353$. Input data is selected in such a way that at least one valid permutation exists.

$^{\text{∗}}$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).

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 2500$). The description of the test cases follows.

The first line of each test case contains an integer $n$ ($2 \le n \le 5000$) — the number of vertices.

The second line of each test case contains $n-1$ integers $fa_2,fa_3,\ldots,fa_n$ ($1 \le fa_i \lt i$)— $fa_i$ is the parent of $i$ on $T$.

The third line of each test case contains $n$ integers $a_1,a_2,\ldots,a_n$ ($0 \le a_i \lt n$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $5000$. Input data is selected in such a way that at least one valid permutation exists.

Output

For each test case, output one integer — the number of permutations modulo $998\,244\,353$.

Note

Visualizer link

In the first test case, the only permutation which satisfies the condition is $[1,2,3,4,5]$.

In the second test case, permutations which satisfy the condition are $[4,5,1,2,3],[4,5,1,3,2],[4,5,2,1,3],[4,5,2,3,1],[4,5,3,1,2],[4,5,3,2,1]$.

In the third test case, permutations which satisfy the condition are $[3,1,6,2,5,7,8,4],[3,1,6,2,5,8,7,4],[3,2,6,1,5,7,8,4],[3,2,6,1,5,8,7,4]$.