// code by 樓影沫瞬_Hz17
#include <bits/stdc++.h>
using namespace std;#define getc() getchar_unlocked()
#define putc(a) putchar_unlocked(a)
#define en_ putc('\n')
#define e_ putc(' ')// #define int long long
using pii = pair<int, int>;template<class T> inline T in() { T n = 0; char p = getc();while(p < '-') p = getc();bool f = p == '-' ? p = getc() : 0;do n = n * 10 + (p ^ 48), p = getc();while(isdigit(p));return f ? -n : n;
}
template<class T> inline T in(T &a) { return a = in<T>(); }
template<class T, class ... Args> inline void in(T &t, Args&... args) { in(t), in(args...); }template<class T> inline void out(T n) {if(n < 0) putc('-'), n = -n;if(n > 9) out(n / 10);putc(n % 10 + '0');
}template<class T1, class T2> T1 max(T1 a, T2 b) { return a > b ? a : a = b;}
template<class T1, class T2> T1 min(T1 a, T2 b) { return a < b ? a : a = b;}constexpr int N = 2e5 + 10, B = 450, T = N / B + 100;int n, Q;#define lb(x) (x & -x)int sum[100][N];inline int qed(int l, int r, int t) { return sum[t][r] - sum[t][l - 1]; }int fa[N], dfn[N], sz[N], wc[N], top[N], dep[N];vector<int> e[N];inline void dfs(int u, int f) {fa[u] = f, dep[u] = dep[f] + 1, sz[u] = 1;for(int v : e[u])if(v != f) {dfs(v, u);sz[u] += sz[v];wc[u] = sz[wc[u]] > sz[v] ? wc[u] : v;}
}bool vis[N];
int pri[5000], cnp;inline void line() {for(int i = 2; i <= 10000; i ++) {if(!vis[i]) pri[++ cnp] = i;for(int j = 1; pri[j] * i <= 10000 and j <= cnp; j ++) {vis[i * pri[j]] = 1;if(i % pri[j] == 0) break;}}
}inline pair<vector<int>, vector<int> > divide(int x) {vector<int> res1, res2;for(int i = 1; i <= cnp; i ++) {if(x == 1) break;if(x % pri[i] == 0) {while(x % pri[i] == 0) {if(i <= 90) res1.push_back(i);else res2.push_back(pri[i]);x /= pri[i];}}}if(x != 1) res2.push_back(x);return {res1, res2};
}int rr[N * 2], st[N], ed[N], cntn, cnto;inline void dfs2(int u, int tp) {top[u] = tp, dfn[u] = ++ cntn; st[u] = ++ cnto, rr[cnto] = u;if(wc[u]) dfs2(wc[u], tp);for(int v : e[u]) if(v != fa[u] and v != wc[u]) dfs2(v, v);ed[u] = ++ cnto, rr[cnto] = u;
}inline int lca(int u, int v) {while(top[u] != top[v]) {if(dep[top[u]] < dep[top[v]]) swap(u, v);u = fa[top[u]];}return dep[u] > dep[v] ? v : u;
}inline int query(int u, int v) {int res[100] = {};while(top[u] != top[v]) {if(dep[top[u]] < dep[top[v]]) swap(u, v);for(int i = 1; i <= 90; i ++) res[i] += qed(dfn[top[u]], dfn[u], i);u = fa[top[u]];}if(dfn[u] < dfn[v]) swap(u, v);int RES = 0;for(int i = 1; i <= 90; i ++) res[i] += qed(dfn[v], dfn[u], i), RES = max(res[i], RES);return RES;
}struct QUE {int l, r, lca, id;
} q[N];
int cnt[N], cntcnt[N], pos[N];
int tim[N];vector<int> num[N];int a[N], ans[N];
int flg[N], mx;inline void add(int i) {for(int v : num[i]) {cntcnt[cnt[v]] --;cnt[v] ++;cntcnt[cnt[v]] ++;mx = max(cnt[v], mx);}
}inline void red(int i) {for(int v : num[i]) {cntcnt[cnt[v]] --;if(cntcnt[cnt[v]] == 0 and mx == cnt[v]) mx --;cnt[v] --;cntcnt[cnt[v]] ++;}
}signed main() {#ifndef ONLINE_JUDGEfreopen("in.ru", "r", stdin);freopen("out.ru", "w", stdout);#endifin(n, Q);line();for(int i = 1; i <= n; i ++) in(a[i]);for(int i = 1, u, v; i < n; i ++) {in(u, v);e[u].push_back(v);e[v].push_back(u);}dfs(1, 1);dfs2(1, 1);vector<int> tmp;for(int i = 1; i <= n; i ++) {auto v = divide(a[i]);tmp = v.first, num[i] = v.second;for(int v : tmp) {sum[v][dfn[i]] ++;}}for(int i = 1; i <= 90; i ++) {for(int j = 1; j <= n; j ++) sum[i][j] += sum[i][j - 1];}vector<int> Hash;for(int i = 1; i <= n; i ++) for(int v : num[i]) Hash.push_back(v);sort(Hash.begin(), Hash.end());Hash.erase(unique(Hash.begin(), Hash.end()), Hash.end());for(int i = 1; i <= n; i ++) for(int&v : num[i]) v = lower_bound(Hash.begin(), Hash.end(), v) - Hash.begin() + 1;for(int i = 1, u, v; i <= Q; i ++) {in(u, v);ans[i] = query(u, v);if(st[u] > st[v]) swap(u, v);int l = lca(u, v);if(l == u) q[i] = {st[u], st[v], 0, i};else q[i] = {ed[u], st[v], l, i};}// partI may okfor(int i = 1; i <= n; i ++) pos[i] = (i - 1) / B + 1;sort(q + 1, q + 1 + Q, [](const QUE&a, const QUE&b) {return pos[a.l] == pos[b.l] ? pos[a.l] & 1 ? a.r < b.r : a.r > b.r : pos[a.l] < pos[b.l];}); for(int l = 1, r = 0, i = 1; i <= Q; i ++) {while(l < q[i].l) {flg[rr[l]] --;if(flg[rr[l]] == 1) add(rr[l]);if(flg[rr[l]] == 0) red(rr[l]);l ++;}while(l > q[i].l) {l --;flg[rr[l]] ++;if(flg[rr[l]] == 1) add(rr[l]);if(flg[rr[l]] == 2) red(rr[l]);}while(r < q[i].r) {r ++;flg[rr[r]] ++;if(flg[rr[r]] == 1) add(rr[r]);if(flg[rr[r]] == 2) red(rr[r]);}while(r > q[i].r) {flg[rr[r]] --;if(flg[rr[r]] == 1) add(rr[r]);if(flg[rr[r]] == 0) red(rr[r]);r --;}if(q[i].lca) add(q[i].lca);ans[q[i].id] = max(ans[q[i].id], mx);if(q[i].lca) red(q[i].lca);}// partII may OKfor(int i = 1; i <= Q; i ++) {out(ans[i]); en_;}
}
// 星間~ 干渉~ 融解~ 輪迴~ 邂逅~ 再生~ ララバイ~
