P12001 在小小的奶龙山里面挖呀挖呀挖

夏天快要到了，去兴绍奶龙山参加 ION5202 的 0p 决定探究奶龙山的性质。

奶龙山内部存在复杂的奶龙山隧道，但是聪明的 0p 一眼就看出了 $n-1$ 条奶龙山隧道的结构是一颗树。其中任意两个隧道只在 $n$ 个休息点处相交，两两休息点之间都有路径联通，第 $i$ 个休息点有一个权值 $a_i$，对于每一个素数 $p$，若 $p\mid a_i$ 则说明 $p$ 公司参与了休息点建设。想要经过一个休息点，就必须和所有参与了休息点建设的公司搞好关系。 0p 有 $q$ 条心仪的路线，第 $i$ 条是从休息点 $u$ 走到休息点 $v$，对于每一条路线，0p 想知道，他需要与多少公司搞好关系才可以成功地走完这一条路线。 **请注意算法常数对时间效率的影响**。

无

无

对于 $20\%$ 的数据，满足 $n,q\leq 100$。 对于 $70\%$ 的数据，满足 $n,q\leq 1000$。 对于 $100\%$ 的数据，满足 $1\leq n,q\leq 5\times 10^4$，$1\leq a_i\leq 10^5$，$1\leq u,v\leq n$，保证给出的树合法。