#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<int,int> pii;
typedef vector<int> vii;
typedef vector<ll> vll;
typedef vector<pii> vpii;
typedef unordered_map<int,int> umap;
typedef long double ld;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define popcount __builtin_popcount
#define case cout<<"Case "<<__testcase-testcase<<": ";


vector<bool> yes;
vector<vii> g;
int cnt=0;
void dfs(int u){
    if(yes[u]) return;
    yes[u]=true;
    cnt++;
    for(auto v: g[u]) dfs(v);
    return;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int testcase=1;
    //cin>>testcase;
    int __testcase=testcase;
    while(testcase--){
        int n,m,i,j,k;
        cin>>n;
        yes.assign(n+5, false);
        g.resize(n+5);
        vii a(n+1); for(i=1;i<=n;i++) cin>>a[i];
        const int N=1000005;
        vii p[N];
        for(i=2;i<N;i++){
            if(p[i].size()) continue;
            for(j=i;j<N;j+=i) p[j].pb(i);
        }
        vii node[N];
        vector<vii> edge[N];
        for(i=1;i<=n;i++){
            if(a[i]==1) continue;
            for(auto j: p[i]) node[j].pb(i);
        }
        //cout<<"done"<<endl;
        for(i=0;i<n-1;i++){
            int u,v;
            cin>>u>>v;
            for(auto j: p[a[u]]){
                if(find(p[a[v]].begin(), p[a[v]].end(), j)==p[a[v]].end()) continue;
                edge[j].pb({u,v});
            }
        }
        //cout<<"done"<<endl;
        int ans=0;
        for(i=2;i<N;i++){
            if(p[i].size()>1) continue;
            //cout<<i<<endl;
            for(auto e: edge[i]){
                g[e[0]].pb(e[1]);
                g[e[1]].pb(e[0]);
            }
            for(auto j: node[i]) yes[j]=false;
            for(auto j: node[i]){
                if(yes[j]) continue;
                cnt=0;
                dfs(j);
                ans=max(ans, cnt);
            }
        }
        cout<<ans<<endl;
    }
}