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

int main()
{
    int dsu[101010],sz[101010];
    
    stack<pair<int*,int>>rbQ;
    auto reset=[&](int v)->void{dsu[v]=v;sz[v]=1;};
    function<int(int)>find=[&](int v)->int{if(v==dsu[v])return v;return dsu[v]=find(dsu[v]);};
    auto merge=[&](int a,int b)->int{a=find(a);b=find(b);if(a!=b){if(sz[a]<sz[b])swap(a,b);rbQ.push({&dsu[b],dsu[b]});rbQ.push({&sz[a],sz[a]});dsu[b]=a;sz[a]+=sz[b];}return sz[a];};
    auto rollback=[&](){while(size(rbQ)){auto[a,b]=rbQ.top();rbQ.pop();*a=b;}};
    int n;cin>>n;
    for(int i=0;i<=n;i++)reset(i);
    int a[n];for(int&i:a)cin>>i;
    bool np[1010101]{1,1};
    vector<int>fact[1010101];
    for(int i=2;i<1010101;i++)if(!np[i])
    {
        cout<<"uwu"<<endl;
        fact[i].push_back(i);
        for(int j=2*i;j<1010101;j+=i)
        {
            fact[j].push_back(i);
            np[i]=1;
        }
    }
    
    vector<pair<int,int>>elist[1010101];
    for(int i=0;i<n;i++)
    {
        int u,v;cin>>u>>v;
        int g=gcd(a[u-1],a[v-1]);
        for(int&x:fact[g])elist[x].emplace_back(u,v);
    }
    
    int ans=0;
    for(int i=0;i<n;i++)if(a[i]>1)ans=1;
    for(int i=2;i<1010101;i++)
    {
        
        if(!np[i])
        {
            for(auto[u,v]:elist[i])ans=max(ans,merge(u,v));
            rollback();
        }
    }
    cout<<ans;
}