Path Company Relationships in Milk Dragon Tunnels

In the Milk Dragon Mountain there exists a complex tunnel network. However, the clever 0p noticed that the structure of the n-1 tunnels forms a tree. The tunnels only intersect at n rest stops and there is a path connecting every pair of them.

Each rest stop i has an associated weight \(a_i\). For every prime \(p\), if \(p\) divides \(a_i\) then it means that company \(p\) participated in the construction of that rest stop. To pass through a rest stop, 0p must have good relations with every company that helped build it.

0p has q desired routes. The \(i\)th query asks: if you travel from rest stop \(u\) to rest stop \(v\), how many distinct companies (i.e. primes) do you need to have good relations with to successfully complete the route? In other words, for each query, you need to find the number of distinct primes that divide \(a_i\) for one or more rest stops along the unique simple u-v path in the tree.

Note on Efficiency: Please be mindful of algorithmic constant factors when designing your solution.

inputFormat

The first line contains two integers \(n\) and \(q\) \( (2 \le n \le 10^5,\; 1 \le q \le 10^5)\) representing the number of rest stops and the number of queries respectively.

The second line contains \(n\) integers \(a_1, a_2, \ldots, a_n\) \( (1 \le a_i \le 10^9)\) representing the weight at each rest stop.

Each of the next \(n-1\) lines contains two integers \(u\) and \(v\) which represent an undirected tunnel connecting rest stops \(u\) and \(v\).

Each of the next \(q\) lines contains two integers \(u\) and \(v\) representing a query asking for the route from rest stop \(u\) to rest stop \(v\).

outputFormat

For each query, output a single integer on a new line: the number of companies (i.e. distinct primes) that 0p needs to be on good terms with to traverse the route from \(u\) to \(v\).

sample

5 3
6 10 15 7 30
1 2
1 3
2 4
2 5
1 4
3 5
4 5

4
3
4