#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#define ssuyu                                                                  \
    ios_base::sync_with_stdio(0);                                              \
    cin.tie(0)
#define pb push_back
#define F first
#define S second
#define pii pair<int, int>
#define int long long
#define PI acos(-1)
#define all(x) (x).begin(), (x).end()
const int N = 1e6 + 5;
int a[N];
int prime[N] = {0}, f[N] = {0};
vector<int> primes;
int Find(int a) {
    if (f[a] <= 0) {
        return a;
    } else
        return f[a] = Find(f[a]);
}
int Union(int a, int b) {
    int fa = Find(a);
    int fb = Find(b);
    if (fa == fb)
        return -f[fa];
    if (f[fa] > f[fb])
        swap(fa, fb);
    f[fa] += f[fb];
    f[fb] = fa;
    return -f[fa];
}
void getprimes(int n) {
    for (int i = 2; i <= n; i++) {
        if (!prime[i]) {
            primes.pb(i);
        }
        for (auto u : primes) {
            if (u * i > n)
                break;
            prime[u * i] = 1;
            if (!(i % u))
                break;
        }
    }
}
struct edge {
    int u;
    int v;
    int w = 1;
} edge[N];
signed main() {
    int n, m, x, y;
    int mx = 0, ans = 0;
    vector<int> affect;
    map<int, vector<pii>> mp;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        mx = max(mx, a[i]);
    }
    getprimes(mx);
    for (int i = 0; i < n - 1; i++) {
        cin >> x >> y;
        f[x] = f[y] = -1;
        int w = __gcd(a[x], a[y]);
        for (int j = 0; i < primes.size() && primes[j] * primes[j] < w; j++) {
            if (w % primes[j] == 0) {
                mp[primes[j]].pb({x, y});
            }
            while (w % primes[j] == 0)
                w /= primes[j];
        }
    }
    for (auto p : mp) {
        for (auto u : p.S) {
            ans = max(Union(u.F, u.S), ans);
            affect.pb(u.F);
            affect.pb(u.S);
        }
        for (auto u : affect)
            f[u] = -1;
        affect.clear();
    }
    cout << ans;
}