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
//package sept;

import java.io.*;
import java.util.*;

public class TimePass implements Runnable {
    InputStream is;
    PrintWriter out;
    String INPUT = "1 2";
    //boolean codechef=false;
    boolean codechef=true;
    static int mod=998244353;
    static int mod2=1000000007;
	static LinkedList<Integer>[] mult;
	static LinkedList<Integer>[] g2;
	static int[][] g;
	static int[] a;
    void solve() throws IOException
	{
    	int n=ni();
    	a=new int[n];
    	int N=200040;
    	mult=new LinkedList[N];
    	g2=new LinkedList[N];
    	for(int i=0;i<N;i++)
    	{
    		mult[i]=new LinkedList<>();
    		g2[i]=new LinkedList<>();
    	}
    	for(int i=0;i<n;i++)
    	{
    		a[i]=ni();
    		int x=a[i];
    		for(int j=2;(long)j*j<=a[i];j++)
    		{
    			if(a[i]%j==0)
    			{
    				mult[j].add(i);
    				while(a[i]%j==0)
    				{
    					a[i]/=j;
    				}
    			}
    		}
    		if(a[i]>1)mult[a[i]].add(i);
    		a[i]=x;
    	}
    	int[] from=new int[2*(n-1)];
    	int[] to=new int[2*(n-1)];
    	int ind=0;
    	for(int i=0;i<n-1;i++)
    	{
    		int u=ni()-1,v=ni()-1;
    		from[ind++]=u;
    		to[ind-1]=v;
    		from[ind++]=v;
    		to[ind-1]=u;
    	}
    	g=packD(n,from,to);
    	ans=0;
    	used=new int[N];
    	cc=0;
    	d=new int[N];
    	for(int p=2;p<N;p++)
    	update(p);
    	
    	out.println(ans);
    	
	}
    
    static int ans;
    
    void update(int p)
    {
    	if(mult[p].isEmpty())return;
    	for(int x:mult[p])
    	{
    		g2[x].clear();
    		for(int y:g[x])
    		{
    			if(a[y]%p==0)
    			{
    				g2[x].add(y);
    			}
    		}
    	}
    	HashSet<Integer> used=new HashSet<>();
    	for(int x:mult[p])
    	{
    		if(!used.contains(x))
    		{
    			Pair z1=bfs(x, used);
    			Pair z2=bfs(z1.a, used);
    			ans=Math.max(ans, z2.b);
    		}
    	}
    }
    
    static int[] used;
    static int cc;
    static int[] d;
    
    
    Pair bfs(int x,HashSet<Integer> set)
    {
    	cc++;
    	Queue<Integer> q=new LinkedList<>();
    	q.offer(x);
    	d[x]=1;
    	used[x]=cc;
    	Pair ans=new Pair(x,d[x],0);
    	while(!q.isEmpty())
    	{
    		int curr=q.poll();
    		set.add(curr);
    		ans.a=curr;
    		ans.b=d[curr];
    		for(int next:g2[curr])
    		{
    			if(used[next]!=cc)
    			{
    				used[next]=cc;
    				d[next]=d[curr]+1;
    				q.offer(next);
    			}
    		}
    	}
    	return ans;
    }
    

	static long fnc(int x,int y)
    {
    	return x+(long)1000000007*y;
    }

	static int[][] packD(int n,int[] from,int[] to)
	{
		int[][] g=new int[n][];
		int[] p=new int[n];
		for(int f:from)
		{
			p[f]++;
		}
		int m=from.length;
		for(int i=0;i<n;i++)
		{
			g[i]=new int[p[i]];
		}
		for(int i=0;i<m;i++)
		{
			g[from[i]][--p[from[i]]]=to[i];
		}
		return g;
	}
	    
    static class Pair
    {
        int a,b,ind;
        public Pair(int a,int b,int ind)
        {
            this.a=a;
            this.b=b;
            this.ind=ind;
        }
    }
    
    static long lcm(int a,int b)
    {
        long val=a;
        val*=b;
        return (val/gcd(a,b));
    }
    
    static long gcd(long a,long b)
    {
        if(a==0)return b;
        return gcd(b%a,a);
    }
    
    static int pow(int a, int b, int p)
    {
        long ans = 1, base = a;
        while (b!=0)
        {
            if ((b & 1)!=0)
            {
                ans *= base;
                ans%= p;
            }
            base *= base;
            base%= p;
            b >>= 1;
        }
        return (int)ans;
    }

    static int inv(int x, int p)
    {
        return pow(x, p - 2, p);
    }
    
    public void run()
    {
        if(codechef)oj=true;
        is = oj ? System.in : new ByteArrayInputStream(INPUT.getBytes());
        out = new PrintWriter(System.out);
        
        long s = System.currentTimeMillis();
        try {
			solve();
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
        out.flush();
        tr(System.currentTimeMillis()-s+"ms");
    }
    
    public static void main(String[] args) throws Exception {new Thread(null,new TimePass(),"Main",1<<26).start();}
    
    private byte[] inbuf = new byte[1024];
    public int lenbuf = 0, ptrbuf = 0;
    
    private int readByte()
    {
        if(lenbuf == -1)throw new InputMismatchException();
        if(ptrbuf >= lenbuf){
            ptrbuf = 0;
            try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
            if(lenbuf <= 0)return -1;
        }
        return inbuf[ptrbuf++];
    }
    
    private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
    private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
    
    private double nd() { return Double.parseDouble(ns()); }
    private char nc() { return (char)skip(); }
    
    private String ns()
    {
        int b = skip();
        StringBuilder sb = new StringBuilder();
        while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }
    
    private char[] ns(int n)
    {
        char[] buf = new char[n];
        int b = skip(), p = 0;
        while(p < n && !(isSpaceChar(b))){
            buf[p++] = (char)b;
            b = readByte();
        }
        return n == p ? buf : Arrays.copyOf(buf, p);
    }
    
    private char[][] nm(int n, int m)
    {
        char[][] map = new char[n][];
        for(int i = 0;i < n;i++)map[i] = ns(m);
        return map;
    }
    
    private int[] na(int n)
    {
        int[] a = new int[n];
        for(int i = 0;i < n;i++)a[i] = ni();
        return a;
    }
    
    private int ni()
    {
        int num = 0, b;
        boolean minus = false;
        while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
        if(b == '-'){
            minus = true;
            b = readByte();
        }
        
        while(true){
            if(b >= '0' && b <= '9'){
                num = num * 10 + (b - '0');
            }else{
                return minus ? -num : num;
            }
            b = readByte();
        }
    }
    
    private long nl()
    {
        long num = 0;
        int b;
        boolean minus = false;
        while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
        if(b == '-'){
            minus = true;
            b = readByte();
        }
        
        while(true){
            if(b >= '0' && b <= '9'){
                num = num * 10 + (b - '0');
            }else{
                return minus ? -num : num;
            }
            b = readByte();
        }
    }
    
    private boolean oj = System.getProperty("ONLINE_JUDGE") != null;
    private void tr(Object... o) { if(!oj)System.out.println(Arrays.deepToString(o)); }
}