#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_map>
#include<vector>
#include<numeric>
#include<cmath>
using namespace std;
#define ll long long
#define ge getchar 
#define pun putchar('\n')
#define pu putchar
#define puk putchar(' ')
#define pb push_back
typedef vector<int> vint;
typedef array<int,2> pii;
const int nn=5006,mm=nn*2;
int n,a[nn],sx,p[25]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97};
int z[nn],x[mm],t[mm];
int ss=0,pr[1400];
void ff(int n,int i){
	if(n>10000)return;
	if(i==25){
		//cout<<++ss<<' '<<n<<endl;
		if(n>1)pr[++ss]=n;
		return;
	}
	ff(n,i+1);
	ff(n*p[i],i+1);
}

vector<pii> dfs(int u,int fu){
	vector<pii> f;
	for(int k=1;k<=ss;k++)f.pb({pr[k],(a[u]==pr[k])?0:pr[k]});
	for(int i=z[u];i;i=x[i]){
		int v=t[i];
		if(v!=fu){
			vector<pii> g=dfs(v,u),r;
			for(auto [x,xx]:f){
				int zx=sx+1;
				for(auto [y,yy]:g)if(__gcd(x,y)>1){
					zx=min(zx,yy);
				}
				if(xx+zx<=sx)r.pb({x,xx+zx});
			}
			f=r;
		}
	}
	return f;
}

int main(){
	ff(1,0);
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		for(int j=0;j<25;j++)while(a[i]/p[j]/p[j]*p[j]*p[j]==a[i])a[i]/=p[j];
	}
	int ki=1;
	for(int i=2;i<=n;i++){
		int u,v;scanf("%d%d",&u,&v);
		x[++ki]=z[u],z[u]=ki,t[ki]=v;
		x[++ki]=z[v],z[v]=ki,t[ki]=u;
	}
	sx=n*2;
	vector<pii> f=dfs(1,0);
	int zx=sx+1;
	for(auto [x,xx]:f)zx=min(zx,xx);
	cout<<zx<<endl;
	return 0;
}