#include <bits/stdc++.h>
#pragma comment(linker, "/STACK:667177216")
using namespace std;
const long long MOD = 1000000000 + 7;
const long long MAXN = 200000 + 100;
template <typename T>
std::ostream& operator<<(std::ostream& out, const std::vector<T>& v) {
  if (!v.empty()) {
    out << '[';
    std::copy(v.begin(), v.end(), std::ostream_iterator<T>(out, ", "));
    out << "\b\b]";
  }
  return out;
}
struct step {
  int p, v, deep;
};
step solve(vector<vector<int>>& g, vector<int>& a, int v, int prime,
           bool decrease) {
  queue<step> q;
  q.push({-1, v, 1});
  int maxi = -1;
  while (!q.empty()) {
    auto cur = q.front();
    maxi = max(maxi, cur.deep);
    q.pop();
    if (decrease) {
      while (a[cur.v] % prime == 0) {
        a[cur.v] /= prime;
      }
    }
    for (int i = 0; i < g[cur.v].size(); ++i) {
      int to = g[cur.v][i];
      if (to == cur.p || a[to] == 1 || a[to] % prime != 0) continue;
      q.push({cur.v, to, cur.deep + 1});
    }
    if (q.empty()) return cur;
  }
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  bool erat[MAXN];
  memset(erat, true, sizeof(erat));
  for (int i = 2; i * i < MAXN; i++) {
    if (erat[i]) {
      for (int j = i + i; j < MAXN; j += i) {
        erat[j] = false;
      }
    }
  }
  vector<int> primes;
  for (int(i) = 2; (i) < MAXN; (i)++)
    if (erat[i]) primes.push_back(i);
  int n;
  scanf("%d", &n);
  vector<int> a(n);
  vector<vector<int>> g(n);
  for (int(i) = 0; (i) < n; (i)++) scanf("%d", &a[i]);
  for (int(i) = 0; (i) < n - 1; (i)++) {
    int f, t;
    scanf("%d%d", &f, &t);
    f--;
    t--;
    g[f].push_back(t);
    g[t].push_back(f);
  }
  int ans = 0;
  for (int i = 0; i < n; ++i) {
    if (a[i] == 1) continue;
    if (erat[a[i]]) {
      step tmp = solve(g, a, i, a[i], false);
      tmp = solve(g, a, tmp.v, a[i], true);
      ans = max(ans, tmp.deep);
    } else {
      for (int j = 0; j < primes.size(); ++j) {
        long long cur = primes[j];
        if (a[i] == 1) break;
        if (erat[a[i]]) {
          step tmp = solve(g, a, i, a[i], false);
          tmp = solve(g, a, tmp.v, a[i], true);
          ans = max(ans, tmp.deep);
          break;
        }
        if (a[i] % cur == 0) {
          step tmp = solve(g, a, i, cur, false);
          tmp = solve(g, a, tmp.v, cur, true);
          ans = max(ans, tmp.deep);
          continue;
        }
        if (cur * cur > a[i]) break;
      }
    }
  }
  cout << ans;
  return 0;
}
