#include <bits/stdc++.h>
using namespace std;
int n;
int a[200005];
vector<int> lst[200005];
bool np[200005];
vector<int> pfac[200005], bodr;
bool check[200005];
int par[200005];
int dp[200005][8][2];
void bfs() {
  queue<int> Q;
  Q.push(1);
  check[1] = true;
  while (!Q.empty()) {
    int v = Q.front();
    Q.pop();
    bodr.push_back(v);
    for (int i = 0; i < lst[v].size(); i++) {
      int nxt = lst[v][i];
      if (!check[nxt]) {
        check[nxt] = true;
        Q.push(nxt);
        par[nxt] = v;
      }
    }
  }
}
int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  for (int i = 1; i < n; i++) {
    int x, y;
    scanf("%d %d", &x, &y);
    lst[x].push_back(y);
    lst[y].push_back(x);
  }
  for (int i = 2; i <= 200000; i++) {
    if (!np[i]) {
      for (int j = i; j <= 200000; j += i) {
        np[j] = true;
        pfac[j].push_back(i);
      }
      np[i] = false;
    }
  }
  bfs();
  for (int i = n - 1; i >= 0; i--) {
    int v = bodr[i];
    int cval = a[v], pval = a[par[v]];
    int csz = pfac[cval].size(), psz = pfac[pval].size();
    int cidx = 0, pidx = 0;
    while (cidx < csz && pidx < psz) {
      if (pfac[cval][cidx] == pfac[pval][pidx]) {
        if (dp[v][cidx][0] + 1 >= dp[par[v]][pidx][0]) {
          dp[par[v]][pidx][1] = dp[par[v]][pidx][0];
          dp[par[v]][pidx][0] = dp[v][cidx][0] + 1;
        } else if (dp[v][cidx][0] + 1 > dp[par[v]][pidx][1]) {
          dp[par[v]][pidx][1] = dp[v][cidx][0] + 1;
        }
        pidx++, cidx++;
      } else if (pfac[cval][cidx] < pfac[pval][pidx])
        cidx++;
      else if (pfac[cval][cidx] > pfac[pval][pidx])
        pidx++;
    }
  }
  int res = 0;
  for (int i = 1; i <= n; i++) {
    if (pfac[a[i]].size() == 0) continue;
    for (int j = 0; j < 6; j++) res = max(res, dp[i][j][0] + dp[i][j][1] + 1);
  }
  printf("%d", res);
  return 0;
}
