You are given a tree consisting of n vertices. A number is written on each vertex; the number on vertex i is equal to a_i.

Let's denote the function g(x, y) as the greatest common divisor of the numbers written on the vertices belonging to the simple path from vertex x to vertex y (including these two vertices). Also let's denote dist(x, y) as the number of vertices on the simple path between vertices x and y, including the endpoints. dist(x, x) = 1 for every vertex x.

Your task is calculate the maximum value of dist(x, y) among such pairs of vertices that g(x, y) > 1.

Input

The first line contains one integer n — the number of vertices (1 ≤ n ≤ 2 ⋅ 10^5).

The second line contains n integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ 2 ⋅ 10^5) — the numbers written on vertices.

Then n - 1 lines follow, each containing two integers x and y (1 ≤ x, y ≤ n, x ≠ y) denoting an edge connecting vertex x with vertex y. It is guaranteed that these edges form a tree.

Output

If there is no pair of vertices x, y such that g(x, y) > 1, print 0. Otherwise print the maximum value of dist(x, y) among such pairs.

Examples

Input

3
2 3 4
1 2
2 3


Output

1


Input

3
2 3 4
1 3
2 3


Output

2


Input

3
1 1 1
1 2
2 3


Output

0
/*Author: Satyajeet Singh, Delhi Technological University*/
import java.io.*;
import java.util.*;
import java.text.*; 
import java.lang.*;
import java.math.*;
public class Main1{
/*********************************************Constants******************************************/
    static PrintWriter out=new PrintWriter(new OutputStreamWriter(System.out));        
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static long mod=(long)1e9+7;
    static long mod1=998244353;
    static boolean sieve[];
    static ArrayList<Integer> primes;
    static ArrayList<Long> factorial;
    static HashSet<Integer> graph[];
/****************************************Solutions Begins*****************************************/
    static int n=0,input[],dp[],dpd[];
    static boolean vis[];
    static int dfs(int start,int par){
       // debug(start);
        if(dp[start]!=-1){
            return dp[start];
        }
        int max=0;
        int smax=0;
        for(int u:graph[start]){
            if(u!=par){
                dfs(u,start);
                if(dp[u]>=max){
                    smax=max;
                    max=dp[u];
                }
                else if(dp[u]>smax){
                    smax=dp[u];
                }
            }
        }
        dp[start]=max+1;
        dpd[start]=max+smax+1;
        return dp[start];
    }
    public static void main (String[] args) throws Exception {
        String st[]=br.readLine().split(" ");
        n=Integer.parseInt(st[0]);
        st=br.readLine().split(" ");
        input=new int[n+1];
        boolean flag=true;
        for(int i=0;i<n;i++){
            input[i+1]=Integer.parseInt(st[i]);
            if(input[i+1]!=1){
                flag=false;
            }
        }
        Makegraph(n+1);
        ArrayList<Integer> list[]=new ArrayList[200005];
        for(int i=0;i<n-1;i++){
            st=br.readLine().split(" ");
            int a=Integer.parseInt(st[0]);
            int b=Integer.parseInt(st[1]);
            int g=(int)gcd(input[a],input[b]);
            if(list[g]==null){
                list[g]=new ArrayList<>();
            }
            list[g].add(a);
            list[g].add(b);
        }

       // debug(list);
        Makegraph(n+1);
        boolean taken[]=new boolean[n+1];
        ArrayList<Integer> cur=new ArrayList<>();
        dp=new int[n+1];
        dpd=new int[n+1];
        Arrays.fill(dp,-1);
        Arrays.fill(dpd,-1);

        sieveMake(200003);
        int ans=0;
        if(!flag)
            ans=1;
        for(int p:primes){
            int i=p;
            while(i<=200000){
                if(list[i]!=null){
                    for(int y=0;y<list[i].size();y+=2){
                        int a=list[i].get(y);
                        int b=list[i].get(y+1);
                        if(!taken[a])
                            cur.add(a);
                        if(!taken[b])
                            cur.add(b);
                        dp[a]=-1;
                        dp[b]=-1;
                        dpd[a]=-1;
                        dpd[b]=-1;
                        addEdge(a,b);
                        addEdge(b,a);
                        taken[a]=true;
                        taken[b]=true;
                    }
                }
                i+=p;
            }
            
            for(int u:cur){
               // debug(u);
                if(dpd[u]==-1)
                dfs(u,u);
                ans=Math.max(ans,dpd[u]);   
            }
            for(int u:cur){
                graph[u].clear();
                taken[u]=false;
                dpd[u]=-1;
                dp[u]=-1;
            }
            cur.clear();
        }
        out.println(ans);
/****************************************Solutions Ends**************************************************/
        out.flush();
        out.close();
    }

/****************************************Template Begins************************************************/
/***************************************Precision Printing**********************************************/
    static void printPrecision(double d){
        DecimalFormat ft = new DecimalFormat("0.00000000000000000"); 
        out.println(ft.format(d));
    }
/******************************************Graph*********************************************************/
    static void Makegraph(int n){
        graph=new HashSet[n];
        for(int i=0;i<n;i++){
            graph[i]=new HashSet<>();
        }
    }
    static void addEdge(int a,int b){
        graph[a].add(b);
    }    
/*********************************************PAIR********************************************************/
    static class PairComp implements Comparator<Pair>{
        public int compare(Pair p1,Pair p2){
            if(p1.u>p2.u){
                return -1;
            }
            else if(p1.u<p2.u){
                return 81;
            }
            else{
                return p2.v-p1.v;
            }
        }
    }
    static class Pair implements Comparable<Pair> {
        int u;
        int v;
        int index=-1;
        public Pair(int u, int v) {
            this.u = u;
            this.v = v;
        }
 
        public int hashCode() {
            int hu = (int) (u ^ (u >>> 32));
            int hv = (int) (v ^ (v >>> 32));
            return 31 * hu + hv;
        }
 
        public boolean equals(Object o) {
            Pair other = (Pair) o;
            return u == other.u && v == other.v;
        }
 
        public int compareTo(Pair other) {
            if(index!=other.index)
                return Long.compare(index, other.index);
            return Long.compare(v, other.v)!=0?Long.compare(v, other.v):Long.compare(u, other.u);
        }
 
        public String toString() {
            return "[u=" + u + ", v=" + v + "]";
        }
    }
/*************************************************Long Pair*************************************************/
    static class PairCompL implements Comparator<Pairl>{
        public int compare(Pairl p1,Pairl p2){
            if(p1.u>p2.u){
                return 1;
            }
            else if(p1.u<p2.u){
                return -1;
            }
            else{
                return (int)(p1.v-p2.v);
            }
        }
    }
    static class Pairl implements Comparable<Pair> {
            long u;
            long v;
            int index=-1;
            public Pairl(long u, long v) {
                this.u = u;
                this.v = v;
            }
    
            public int hashCode() {
                int hu = (int) (u ^ (u >>> 32));
                int hv = (int) (v ^ (v >>> 32));
                return 31 * hu + hv;
            }
    
            public boolean equals(Object o) {
                Pair other = (Pair) o;
                return u == other.u && v == other.v;
            }
    
            public int compareTo(Pair other) {
                if(index!=other.index)
                    return Long.compare(index, other.index);
                return Long.compare(v, other.v)!=0?Long.compare(v, other.v):Long.compare(u, other.u);
            }
    
            public String toString() {
                return "[u=" + u + ", v=" + v + "]";
            }
        }
/*****************************************DEBUG***********************************************************/
    public static void debug(Object... o) {
        System.out.println(Arrays.deepToString(o));
    }
/************************************MODULAR EXPONENTIATION***********************************************/
    static long modulo(long a,long b,long c) {
        long x=1;
        long y=a;
        while(b > 0){
            if(b%2 == 1){
                x=(x*y)%c;
            }
            y = (y*y)%c; // squaring the base
            b /= 2;
        }
        return  x%c;
    }
/********************************************GCD**********************************************************/
    static long gcd(long x, long y)
    {
        if(x==0)
            return y;
        if(y==0)
            return x;
        long r=0, a, b;
        a = (x > y) ? x : y; // a is greater number
        b = (x < y) ? x : y; // b is smaller number
        r = b;
        while(a % b != 0)
        {
            r = a % b;
            a = b;
            b = r;
        }
        return r;
    }
/******************************************SIEVE**********************************************************/
    static void sieveMake(int n){
        sieve=new boolean[n];
        Arrays.fill(sieve,true);
        sieve[0]=false;
        sieve[1]=false;
        for(int i=2;i*i<n;i++){
            if(sieve[i]){
                for(int j=i*i;j<n;j+=i){
                    sieve[j]=false;
                }
            }
        }
        primes=new ArrayList<Integer>();
        for(int i=0;i<n;i++){
            if(sieve[i]){
                primes.add(i);
            }
        }        
    }
/********************************************End***********************************************************/
}

