#include<bits/stdc++.h> /* SURAJ PRAKASH NARAYAN, CSE, MNNIT Alld, ad-astra */
using namespace std;
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
using namespace __gnu_pbds;
#define fast ios_base::sync_with_stdio(0); cin.tie(0);
#define deb1(x) cout<<#x<<" :: "<<x<<"\n";
#define deb2(x,y) cout<<#x<<" :: "<<x<<"\t"<<#y<<" :: "<<y<<"\n";
#define deb3(x,y,z) cout<<#x<<" :: "<<x<<"\t"<<#y<<" :: "<<y<<"\t"<<#z<<" :: "<<z<<"\n";
#define trace(a) cout<<#a<<"\n";
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define ll long long
#define dd double
#define beg(a) a.begin(),a.end()
#define forr(a,b,n) for(int a=b;a<=n;++a)
#define pll pair<ll,ll>
#define vi std::vector<int>
#define vll vector<ll>
#define vp vector<pll>
#define mii std::map<int,int>
#define mll std::map<ll,ll>
#define si set<int>
#define sll set<ll>
#define sp set<pll>
#define ms0(arr) memset(arr,0,sizeof(arr));
#define ms1(arr) memset(arr,1,sizeof(arr));
#define ms_1(arr) memset(arr,-1,sizeof(arr));
#define sz(a) a.size()
typedef tree<
pll,
null_type,
less<pll>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
//S.order_of_key(pii(sum - t, 1e9));
const int N = 1e6+5;
const ll MOD = 998244353;
const double eps = 1e-6;
//............................................................................................................
int values[200005];
int maxl,ans;
std::vector<int> adj[200005];
int dfs(int v,int p,int gcd){
int maxx = 0,smax = 0;
int a = __gcd(gcd,values[v]);
for(auto it:adj[v]){
int len=0;
if(it!=p)
len = dfs(it,v,(a>1)?a:values[v]);
if(len>=maxx){
smax = maxx,maxx=len;
}
}
if(maxx>0){
ans = max(ans,maxx+smax+1);
return (a>1)?maxx+1:0;
}else if(values[v]>1){
ans = max(ans,1);
return (a>1)?1:0;
}else if(values[v]==1){
return 0;
}
}
int main(int argc, char const *argv[])
{ fast
int n;
cin>>n;
for(int i=1;i<=n;++i){
cin>>values[i];
}
for(int i=0;i<n-1;++i){
int a,b;
cin>>a>>b;
adj[a].pb(b);
adj[b].pb(a);
}
dfs(1,1,0);
cout<<ans;
}
I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4gLyogU1VSQUogUFJBS0FTSCBOQVJBWUFOLCBDU0UsIE1OTklUIEFsbGQsIGFkLWFzdHJhICovCnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgojaW5jbHVkZSA8ZXh0L3BiX2RzL2Fzc29jX2NvbnRhaW5lci5ocHA+IC8vIENvbW1vbiBmaWxlCiNpbmNsdWRlIDxleHQvcGJfZHMvdHJlZV9wb2xpY3kuaHBwPiAvLyBJbmNsdWRpbmcgdHJlZV9vcmRlcl9zdGF0aXN0aWNzX25vZGVfdXBkYXRlCnVzaW5nIG5hbWVzcGFjZSBfX2dudV9wYmRzOwoKI2RlZmluZSBmYXN0IGlvc19iYXNlOjpzeW5jX3dpdGhfc3RkaW8oMCk7IGNpbi50aWUoMCk7CiNkZWZpbmUgZGViMSh4KSBjb3V0PDwjeDw8IiA6OiAiPDx4PDwiXG4iOwojZGVmaW5lIGRlYjIoeCx5KSBjb3V0PDwjeDw8IiA6OiAiPDx4PDwiXHQiPDwjeTw8IiA6OiAiPDx5PDwiXG4iOwojZGVmaW5lIGRlYjMoeCx5LHopIGNvdXQ8PCN4PDwiIDo6ICI8PHg8PCJcdCI8PCN5PDwiIDo6ICI8PHk8PCJcdCI8PCN6PDwiIDo6ICI8PHo8PCJcbiI7CiNkZWZpbmUgdHJhY2UoYSkgY291dDw8I2E8PCJcbiI7CgoKI2RlZmluZSBtcCBtYWtlX3BhaXIKI2RlZmluZSBwYiBwdXNoX2JhY2sKI2RlZmluZSBGIGZpcnN0CiNkZWZpbmUgUyBzZWNvbmQKI2RlZmluZSBsbCBsb25nIGxvbmcKI2RlZmluZSBkZCBkb3VibGUKI2RlZmluZSBiZWcoYSkgYS5iZWdpbigpLGEuZW5kKCkKCiNkZWZpbmUgZm9ycihhLGIsbikgZm9yKGludCBhPWI7YTw9bjsrK2EpCiNkZWZpbmUgcGxsIHBhaXI8bGwsbGw+CiNkZWZpbmUgdmkgc3RkOjp2ZWN0b3I8aW50PgojZGVmaW5lIHZsbCB2ZWN0b3I8bGw+CiNkZWZpbmUgdnAgdmVjdG9yPHBsbD4KCiNkZWZpbmUgbWlpIHN0ZDo6bWFwPGludCxpbnQ+CiNkZWZpbmUgbWxsIHN0ZDo6bWFwPGxsLGxsPgoKCiNkZWZpbmUgc2kgc2V0PGludD4KI2RlZmluZSBzbGwgc2V0PGxsPgojZGVmaW5lIHNwIHNldDxwbGw+CgojZGVmaW5lIG1zMChhcnIpIG1lbXNldChhcnIsMCxzaXplb2YoYXJyKSk7CiNkZWZpbmUgbXMxKGFycikgbWVtc2V0KGFyciwxLHNpemVvZihhcnIpKTsKI2RlZmluZSBtc18xKGFycikgbWVtc2V0KGFyciwtMSxzaXplb2YoYXJyKSk7CiNkZWZpbmUgc3ooYSkgYS5zaXplKCkKCnR5cGVkZWYgdHJlZTwKcGxsLApudWxsX3R5cGUsCmxlc3M8cGxsPiwKcmJfdHJlZV90YWcsCnRyZWVfb3JkZXJfc3RhdGlzdGljc19ub2RlX3VwZGF0ZT4Kb3JkZXJlZF9zZXQ7Ci8vUy5vcmRlcl9vZl9rZXkocGlpKHN1bSAtIHQsIDFlOSkpOwoKY29uc3QgaW50IE4gPSAxZTYrNTsKY29uc3QgbGwgIE1PRCAgPSA5OTgyNDQzNTM7CmNvbnN0IGRvdWJsZSBlcHMgPSAxZS02OwovLy4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLi4uLgppbnQgdmFsdWVzWzIwMDAwNV07CmludCBtYXhsLGFuczsKc3RkOjp2ZWN0b3I8aW50PiBhZGpbMjAwMDA1XTsKCmludCBkZnMoaW50IHYsaW50IHAsaW50IGdjZCl7CglpbnQgbWF4eCA9IDAsc21heCA9IDA7CglpbnQgYSA9IF9fZ2NkKGdjZCx2YWx1ZXNbdl0pOwoKCWZvcihhdXRvIGl0OmFkalt2XSl7CgkJaW50IGxlbj0wOwoJCWlmKGl0IT1wKQoJCQkgbGVuID0gZGZzKGl0LHYsKGE+MSk/YTp2YWx1ZXNbdl0pOwoJCWlmKGxlbj49bWF4eCl7CgkJCXNtYXggPSBtYXh4LG1heHg9bGVuOwoJCX0KCX0KCWlmKG1heHg+MCl7CgkJYW5zID0gbWF4KGFucyxtYXh4K3NtYXgrMSk7CgkJcmV0dXJuIChhPjEpP21heHgrMTowOwoJfWVsc2UgaWYodmFsdWVzW3ZdPjEpewoJCWFucyA9IG1heChhbnMsMSk7CgkJcmV0dXJuIChhPjEpPzE6MDsKCX1lbHNlIGlmKHZhbHVlc1t2XT09MSl7CgkJcmV0dXJuIDA7Cgl9CgoJCn0KCmludCBtYWluKGludCBhcmdjLCBjaGFyIGNvbnN0ICphcmd2W10pCnsJZmFzdAoJaW50IG47CgljaW4+Pm47Cglmb3IoaW50IGk9MTtpPD1uOysraSl7CgkJY2luPj52YWx1ZXNbaV07Cgl9Cglmb3IoaW50IGk9MDtpPG4tMTsrK2kpewoJCWludCBhLGI7CgkJY2luPj5hPj5iOwoJCWFkalthXS5wYihiKTsKCQlhZGpbYl0ucGIoYSk7Cgl9CgkKCQkJZGZzKDEsMSwwKTsKCQoJY291dDw8YW5zOwoJCn0KCgoKCgogICAKCiAgIAoK