Union of Prime Companies on Tree Paths

There is a tree with n nodes (rest points) and n-1 tunnels. Every node i has a weight \(a_i\). For every prime \(p\), if \(p\) divides \(a_i\), then company \(p\) has participated in building node i. To pass through a node, one needs to have a good relationship with all companies that have contributed to that node.

0p has q desired routes. The i-th query is to travel from node \(u\) to node \(v\). For each route, determine the number of distinct companies (i.e. distinct prime factors from all nodes on the unique path from \(u\) to \(v\)) with whom 0p must have a relationship.

Note: Efficient handling of queries is required.

inputFormat

The first line contains an integer \(n\) (\(1 \leq n \leq \text{some limit}\)), the number of rest points.

The second line contains \(n\) integers: \(a_1, a_2, \dots, a_n\), where \(a_i\) is the weight of the \(i\)-th rest point.

Each of the next \(n-1\) lines contains two integers \(u\) and \(v\), indicating there is a tunnel connecting rest points \(u\) and \(v\). It is guaranteed that these \(n-1\) tunnels form a tree.

The next line contains an integer \(q\), the number of queries.

Each of the following \(q\) lines contains two integers \(u\) and \(v\) representing a query from rest point \(u\) to rest point \(v\).

outputFormat

For each query, output a single integer on a separate line: the number of companies (i.e. distinct prime factors) 0p needs to have relationships with along the route from \(u\) to \(v\).

sample

3
6 10 15
1 2
1 3
2
2 3
1 3

3
2