题目描述

给你一棵由 $n$ 个节点的树和一个数 $x$，其中每个节点都有一个值。问有多少条简单路径的值的 $lcm$ 为 $x$？

一条简单路径的 $lcm$ 的定义为路径上所有节点的值的 $lcm$。

输入格式

第一行输入一个整数 $T$ $(1 \le T \le 200)$，表示测试的总数。

对于每个测试样例：

• 第一行输入两个数 $n$ $(1 \le n \le 10^5)$，$x$ $(2 \le x \le 10^7)$，表示节点的个数和目标值 $x$。
• 接下来 $n-1$ 行，每行两个数 $u,v$，表示节点 $u$ 和 $v$ 之间存在一条边。
• 接下来一行 $n$ 个数 $a_1,a_2,\dots,a_n$ $(1 \le a_i \le 10^9)$，表示每个节点的值。

保证所有样例中 $n$ 的总和不超过 $3 \times 10^5$。

输出格式

对于每个样例，输出一个整数，表示满足条件的路径的数量。

样例

输入

2
3 2
1 2
2 3
2 2 2

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

输出

6
5

样例解释

对于第一个样例，任何路径都满足条件。因此答案为 $3 \times 2 = 6$。

对于第二个样例，满足条件的路径为 $[1,1], [1,2], [1,4], [1,5], [4,5]$。因此答案为 $5$。