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
import java.util.*;
import java.io.*;
//import java.math.*;

public class Task{
        //  ..............code begins here..............

static long mod=(long)1e9+7;
static List<Integer>[] g;
static int[] spf=new int[200001],a;
static Map<Integer,Integer>[] map;
static int res=0;

static void spf(){
    for(int i=2;(long)i*i<=200000;i++){
        if(spf[i]!=0) continue;
        spf[i]=i;
        for(int j=i*i;j<=200000;j+=i){
            if(spf[j]==0) spf[j]=i;
        }
    }
    for(int i=2;i<=200000;i++)
        if(spf[i]==0)spf[i]=i;
}

static void dfs(int s,int p){
    for(int c:g[s]){
        if(c!=p) dfs(c,s);
    }
    int v=a[s-1];
    while(v!=1){
        int p1=spf[v];
        while(v%p1==0) v/=p1;
        List<Integer> l=new ArrayList<>();l.add(0);l.add(0);
        for(int c:g[s]){
            if(c!=p){
                if(map[c].get(p1)!=null) l.add(map[c].get(p1));
            }
        }
        Collections.sort(l);int x=l.size();
        int tmp=l.get(x-1)+l.get(x-2)+1;
        res=Math.max(res,tmp);
        map[s].put(p1,l.get(x-1)+1);
    }
}
static void solve() throws  IOException {
            int n=int_v(read());
            a=int_arr();
            g=new ArrayList[n+1];
            map=new HashMap[n+1];
            for(int i=0;i<=n;i++){
                g[i]=new ArrayList<>();
                map[i]=new HashMap<>();
            }
            for(int i=0;i<n-1;i++){
                int[] e=int_arr();
                g[e[0]].add(e[1]);
                g[e[1]].add(e[0]);
            }
            spf();
            dfs(1,-1);
            out.write(res+"");
}
   
public static void main(String[] args) throws  IOException{
                assign();
                int t=1;//int_v(read());
                while(t--!=0) solve();
                out.flush();
}

// taking inputs
static long pow1(long a,int p){long res=1;while(p>0){if((p&1)!=0){res=(res*a);}p >>=1;a=(a*a);}return res;}

static BufferedReader s1;
static BufferedWriter out;
static String read() throws IOException{String line="";while(line.length()==0){line=s1.readLine();continue;}return line;}
static int int_v (String s1){return Integer.parseInt(s1);}
static long long_v(String s1){return Long.parseLong(s1);}
static void sort(int[] a){List<Integer> l=new ArrayList<>();for(int x:a){l.add(x);}Collections.sort(l);for(int i=0;i<a.length;i++){a[i]=l.get(i);}}
static int[] int_arr() throws IOException{String[] a=read().split(" ");int[] b=new int[a.length];for(int i=0;i<a.length;i++){b[i]=int_v(a[i]);}return b;}
static long[] long_arr() throws IOException{String[] a=read().split(" ");long[] b=new long[a.length];for(int i=0;i<a.length;i++){b[i]=long_v(a[i]);}return b;}
static void assign(){s1=new BufferedReader(new InputStreamReader(System.in));out=new BufferedWriter(new OutputStreamWriter(System.out));}
}