#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> g;
vector<int> a;
int n;
vector<map<int, int>> dp;
int ans = 0;
int gcd(int a, int b) {
  while (b) {
    a %= b;
    swap(a, b);
  }
  return a;
}
void dfs(int v, int p = -1) {
  for (auto to : g[v]) {
    if (to != p) {
      dfs(to, v);
      if (gcd(a[v], a[to]) != 1) {
        for (auto i : dp[to]) {
          int y = gcd(a[v], i.first);
          if (y != 1) {
            for (auto c : dp[v])
              if (gcd(c.first, i.first) != 1)
                ans = max(ans, i.second + c.second);
          }
        }
        for (auto i : dp[to]) {
          int y = gcd(a[v], i.first);
          if (y != 1) {
            dp[v][y] = max(dp[v][y], i.second + 1);
            ans = max(ans, i.second + 1);
          }
        }
      }
    }
  }
}
signed main() {
  std::ios_base::sync_with_stdio(0), cin.tie(0);
  cin >> n;
  g.resize(n);
  a.resize(n);
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
  }
  dp.resize(n);
  for (int i = 0; i < n - 1; ++i) {
    int x, y;
    cin >> x >> y;
    x--, y--;
    g[x].push_back(y);
    g[y].push_back(x);
  }
  for (int i = 0; i < n; ++i) {
    if (a[i] != 1) {
      ans = 1;
      dp[i][a[i]] = 1;
    }
  }
  if (!ans) {
    cout << 0;
    return 0;
  }
  dfs(0);
  cout << ans;
  return 0;
}
