You are given an unrooted tree with $n$ nodes, labeled $1, 2, \dots, n$. The distance between two nodes $i$ and $j$, denoted by $dis(i, j)$, is defined as the number of edges on the simple path between $i$ and $j$ in the tree.

There are $k$ key nodes $a_1, a_2, \dots, a_k$. For every node $v$, we want to find the key node closest to it. Specifically, for a node $v$, let $f(v)$ be the index $i$ that minimizes $dis(v, a_i)$. If there are multiple such indices $i$, we choose the smallest one.

Given $f(1), f(2), \dots, f(n)$, determine how many possible sets $(a_1, a_2, \dots, a_k)$ satisfy these conditions. Since the answer may be very large, output the result modulo $998244353$.

Input

The input consists of multiple test cases. The first line contains an integer $T$, representing the number of test cases.

For each test case, the first line contains two integers $n$ and $k$, representing the number of nodes and the number of key nodes, respectively.

The next $n - 1$ lines each contain two integers $u, v$, representing a tree edge $(u, v)$.

The next line contains $n$ integers $f(1), f(2), \dots, f(n)$. Note: The data does not guarantee that a valid set $(a_1, a_2, \dots, a_k)$ exists.

Output

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

Examples

Input 1

3
3 3
1 2
2 3
1 2 1
3 2
1 2
2 3
1 2 2
3 2
1 2
2 3
2 1 1

Output 1

0
1
2

Input 2

1
10 5
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
1 1 2 2 3 3 4 4 5 5

Output 2

13

Note

In the first example, for the second test case, one solution is $(1, 2)$. For the third test case, two solutions are $(2, 1)$ and $(3, 1)$. Note that when multiple nodes are at the same distance, we choose the smallest index $i$, not $a_i$.

Examples 3 and 4

See the provided files voronoi/voronoi3.in and voronoi/voronoi3.ans for Example 3, which satisfies the constraints for test cases 3–4. See the provided files voronoi/voronoi4.in and voronoi/voronoi4.ans for Example 4, which satisfies the constraints for test cases 7–10.

Constraints

For all data, it is guaranteed that $1 \le T \le 10$, $2 \le k \le n \le 3 \times 10^3$, and $1 \le f(i) \le k$. The details are as follows:

Special Property A: The tree is guaranteed to be a chain. Special Property B: It is guaranteed that $k = 2$.