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

int main()
{
    cin.tie(0)->sync_with_stdio(0);
    int dsu[101010],sz[101010];
    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){a=find(a);b=find(b);if(a!=b){if(sz[a]<sz[b])swap(a,b);dsu[b]=a;sz[a]+=sz[b];}};
    int n;cin>>n;
    for(int i=0;i<=n;i++)reset(i);
    int a[n];for(int&i:a)cin>>i;
    for(int i=0;i<n-1;i++)
    {
        int o,p;cin>>o>>p;
        if(gcd(a[o-1],a[p-1])>1)merge(o,p);
    }
    int msz=0;
    for(int i=1;i<=n;i++)
    {
        if(sz[i]>1||a[i-1]>1)msz=max(sz[i],msz);
    }
    cout<<msz;
}