#include <bits/stdc++.h>
using namespace std;
const int MAX = 2e5 + 4;
int n, a[MAX], ans, counter, vst[MAX], d[MAX];
vector<int> adj[MAX], dbp[MAX], g[MAX];
set<int> primes;
int gcd(int x, int y) {
  if (x < y) swap(x, y);
  if (y == 0) return x;
  return gcd(y, x % y);
}
pair<int, int> bfs(int u, set<int>& used) {
  counter++;
  queue<int> q;
  q.push(u);
  d[u] = 1;
  vst[u] = counter;
  pair<int, int> ret = {u, d[u]};
  while (!q.empty()) {
    int curr = q.front();
    q.pop();
    used.insert(curr);
    ret = {curr, d[curr]};
    for (int next : g[curr]) {
      if (vst[next] != counter) {
        vst[next] = counter;
        d[next] = d[curr] + 1;
        q.push(next);
      }
    }
  }
  return ret;
}
void go(int p) {
  if (dbp[p].empty()) return;
  for (int u : dbp[p]) {
    g[u].clear();
    for (int v : adj[u])
      if (a[v] % p == 0) g[u].push_back(v);
  }
  set<int> used;
  for (int u : dbp[p])
    if (!used.count(u)) {
      pair<int, int> vd = bfs(u, used);
      pair<int, int> vd2 = bfs(vd.first, used);
      ans = max(ans, vd2.second);
    }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  ;
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    int t = a[i];
    for (long long j = 2; j * j <= t; j++) {
      if (t % j == 0) {
        primes.insert(j);
        dbp[j].push_back(i);
        while (t % j == 0) t /= j;
      }
    }
    if (t > 1) {
      primes.insert(t);
      dbp[t].push_back(i);
    }
  }
  for (int i = 0, u, v; i < n - 1; i++) {
    cin >> u >> v;
    if (gcd(a[u], a[v]) != 1) {
      adj[u].push_back(v);
      adj[v].push_back(u);
    }
  }
  for (int i : primes) go(i);
  cout << ans << '\n';
}
