Prof.Chen 正在练习烤蛋糕。在他的大房子花园里，有一棵包含 $n$ 个顶点的配料树，顶点编号为 $1, 2, \dots, n$。在树的第 $i$ 个顶点上，有 $c_i$ 个甜糖。

制作一个蛋糕需要消耗恰好 $k$ 个甜糖。每次在烤新蛋糕之前，Prof.Chen 会来到花园，从树中选择一个连通分量（或整棵树），将其切下，并取走其中的所有甜糖。当一个连通分量被切下时，原树可能会分裂成若干个互不相连的新树。此外，请注意浪费甜糖是不好的，因此 Prof.Chen 总是会确保所选连通分量中的甜糖总数恰好为 $k$。

Prof.Chen 希望尽可能多地制作蛋糕。请帮助 Prof.Chen 确定他最多能制作多少个蛋糕。

输入格式

第一行包含一个整数 $t$ ($1 \le t \le 10^6$)，表示测试用例的数量。对于每个测试用例：

第一行包含两个整数 $n$ 和 $k$ ($1 \le n \le 10^6, 1 \le k \le 2 \cdot 10^6$)，分别表示顶点数量和每个蛋糕所需的甜糖数量。

下一行包含 $n$ 个整数 $c_1, c_2, \dots, c_n$ ($0 \le c_i \le 2$)，表示每个顶点上的甜糖数量。

接下来的 $n - 1$ 行，每行包含两个整数 $u_i$ 和 $v_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$)，描述了连接第 $u_i$ 个顶点和第 $v_i$ 个顶点的无向树边。保证这些边构成一棵树。

保证所有测试用例中 $n$ 的总和不超过 $10^6$。

输出格式

对于每个测试用例，输出一行，包含一个整数，表示 Prof.Chen 最多能制作的蛋糕数量。

样例

样例输入 1

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

样例输出 1

2
0
1
0