#include <bits/stdc++.h>
using namespace std;

#define fileio() freopen("input.txt","r",stdin); freopen("output.txt","w",stdout)
#define fio() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) (x).begin(), (x).end()
#define allr(x) x.rbegin(), x.rend()
#define cmprs(x) sort(all(x)),x.erase(unique(all(x)),x.end())
#define endl "\n"
#define sp " "
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define F first
#define S second
#define rz resize
#define sz(a) (int)(a.size())
#define clr(a) a.clear()

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, ll> pil;
typedef tuple<int, int, int> tpi;
typedef tuple<ll, ll, ll> tpl;
typedef pair<double, ll> pdl;
typedef pair<double, int> pdi;

const int dx[] = {1,-1,0,0,1,1,-1,-1};
const int dy[] = {0,0,1,-1,1,-1,1,-1};
const ll MOD = 1e9+7;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const int MAXN = 101010; // PLZ CHK!
const int MAXA = 1010101;

int mp[MAXA];
void sv() {
    for (int i=2; i<MAXA; i++) mp[i]=i;
    for (int i=4; i<MAXA; i+=2) mp[i]=2;
    for (int i=3; i*i<MAXA; i++) {
        if (mp[i]!=i) continue;
        for (int j=i*i; j<MAXA; j+=i) mp[j]=i;
    }
}

vector<int> fct(int x) {
    vector<int> ret;
    while (x != 1) {
        ret.push_back(mp[x]);
        x=x/mp[x];
    }
    return ret;
}

struct dsu {
    int n;
    vector<int> p,s;
    void init(int _n) {
        n=_n+10;
        p.assign(n,0),s.assign(n,1);
        iota(all(p),0);
    }

    int fd(int a) {
        if (a==p[a]) return a;
        return p[a]=fd(p[a]);
    }

    int mg(int a, int b) {
        a=fd(a), b=fd(b);
        if (a==b) return 0;
        s[a]+=s[b], s[b]=0, p[b]=a;
        return 1; 
    }
};

int N,A[MAXN];
pii E[MAXN];
vector<pii> G[MAXA];
dsu D;

int main() {
    fio();
    sv();

    cin>>N;
    for (int i=1; i<=N; i++) cin>>A[i];    

    D.init(N);
    for (int i=1; i<N; i++) {
        int u,v; cin>>u>>v;
        E[i]={u,v};
        vector<int> f=fct(gcd(A[u],A[v]));
        for (int x:f) G[x].pb(E[i]);
    }

    int ans=0;
    for (int i=2; i<MAXA; i++) {
        if (G[i].empty()) continue;
        // cout<<i<<": ";
        // for (auto [u,v]:G[i]) cout<<u<<sp<<v<<endl;

        for (auto [u,v]:G[i]) D.mg(u,v);
        for (auto [u,v]:G[i]) {
            u=D.fd(u),v=D.fd(v);
            ans=max(ans, D.s[u]);
            ans=max(ans, D.s[v]);
        }
        for (auto [u,v]:G[i]) {
            D.p[u]=u, D.p[v]=v;
            D.s[u]=1, D.s[v]=1;
        }
    }

    cout<<ans;

    return 0;
}