K. Least Common Route
time limit per test
2 s
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a tree of $$$n$$$ nodes. Each node $$$i$$$ has a value $$$a_i$$$. Count the number of simple paths where the LCM of the values of the nodes on the path equals $$$X$$$. In other words, count the number of pairs of nodes $$$u,v$$$ $$$(1 \le u \le v \le n)$$$ where the LCM(Least Common Multiple) of the values $$$a_i$$$ of the nodes on the simple path between $$$u$$$ and $$$v$$$ is equal to $$$X$$$.

Input

The first line contains two integers $$$n,X \: (1 \le n \le 10^5)(1 \le X \le 10^6)$$$.

The second line contains $$$n$$$ integers $$$a_i \: (1 \le a_i \le 10^6)$$$ — the values of the nodes.

Each of the following $$$n-1$$$ lines contains two integers $$$u,v \: (1 \le u,v \le n)(u \neq v)$$$ — the edges of the tree.

It is guaranteed that the edges form a tree.

Output

Print a single integer — the number of paths with LCM equal to $$$X$$$.

Example
Input
7 12
1 5 2 12 4 3 6
1 2
5 1
1 3
4 2
7 3
6 3
Output
3