You are given a tree consisting of N nodes and another integer K, where the $i^{th}$ node has value equal to $v[i]$.

Now, we call the value of a sub-tree the number of distinct $v[i]$ among all nodes it contains. You need to find the number of sub-trees of this tree having value $\le K$ .

A sub-tree of a tree is a subset of nodes and edges of the tree that form a single connected component.

Input: :

Input starts with an integer $( 1 \le T \le 15)$ denoting the number of test cases. Each case starts with two positive integers N and K.

The next line consists of N space separated integers, where the $i^{th}$ integer denotes $v[i]$. Each of the next $N-1$ lines contains 2 space separated integers u and v, denoting an edge between nodes u and v,

Output:

For each test case, print the answer on a new line.

Constraints:

$1 \le T \le 15$

$2 \le N \le 18$

$1 \le K \le N$

$0 \le v[i] \le 10^9$

$1 \le u,v \le N$