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.concurrent.*;
import java.util.*;
import java.io.*;
//import javafx.util.Pair;
public class Main implements Runnable 
{  
    
    class Pair implements Comparable <Pair>
    {
        int x,y,z;
        Pair(int x,int y,int z)
        {
            this.x=x;
            this.y=y;
            this.z=z;
        }
        public int compareTo(Pair p)
        {
            if(x==p.x)
                return Integer.compare(y,p.y);
            else
                return Integer.compare(x,p.x);
        }
    }
    
    public static void main(String[] args)
    {
        new Thread(null, new Main(), "rev", 1 << 29).start();
    }

    public void run()
    {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        Task solver = new Task();
        solver.solve(1,in,out);
        out.close();
    }
    
    static class Task
    { 
        ArrayList <Integer>adj1[],adj2[],adj3[];
        HashSet <Integer>hs=new HashSet<>();
        int []a;
        int n,max=1;
        
        int bfs(int s)
        {
            Queue <Integer>q=new LinkedList<>();
            q.add(s);
            int res=0;
            while(!q.isEmpty())
            {
                 res=q.poll();
                 for(int i:adj3[res])
                     if(!hs.contains(i))
                     {
                         hs.add(i);
                         q.add(i);
                     }
            }
            return res;
        }
        
        int bfs1(int s)
        {
            HashSet <Integer>hs=new HashSet<>();
            Queue <Integer>q=new LinkedList<>();
            q.add(s);
            q.add(-1);
            hs.add(s);
            int res,ct=0;
            while(true)
            {
                res=q.poll();
                if(res==-1)
                {
                    ct++;
                    if(q.isEmpty())
                        break;
                    q.add(-1); 
                    continue;
                }
                for(int i:adj3[res])
                    if(!hs.contains(i))
                    {
                        hs.add(i);
                        q.add(i);
                    }
            }
            return ct;
        }
        
        void check(int p)
        {
            if(adj2[p].isEmpty())
                return;
            /*for(int i=1;i<=n;i++)
                adj3[i].clear();*/
            for(int i:adj2[p])
            {
                adj3[i].clear();
                for(int j:adj1[i])
                    if(a[j]%p==0)
                        adj3[i].add(j);
            }
            /*for(int i=1;i<=n;i++)
            {
                for(int j:adj3[i])
                    System.out.print(j+" ");
                System.out.println();
            }*/
            hs.clear();
            for(int i:adj2[p])
                if(!hs.contains(i) && !adj3[i].isEmpty())
                {
                    hs.add(i);
                    max=Math.max(max,bfs1(bfs(i)));
                }
        }
        
        void solve(int testNumber, InputReader in, PrintWriter out)
        {
            int []min=new int[200001];
            for(int i=1;i<=200000;i++)
                min[i]=i;
            for(int i=2;i*i<=200000;i++)
            {
                if(min[i]==i)
                    for(int j=2*i;j<=200000;j+=i)
                        min[j]=i;
            }
            adj2=new ArrayList[200001];
            for(int i=1;i<=200000;i++)
                adj2[i]=new ArrayList<>();
            n=in.nextInt(); 
            adj1=new ArrayList[n+1];
            for(int i=1;i<=n;i++)
                adj1[i]=new ArrayList<>();
            adj3=new ArrayList[n+1];
            for(int i=1;i<=n;i++)
                adj3[i]=new ArrayList<>();
            a=new int[n+1];           
            int x,y,max1=0;
            for(int i=1;i<=n;i++)
            {
                a[i]=in.nextInt();
                max1=Math.max(max1,a[i]);
                x=a[i];
                while(x!=1)
                {
                    y=min[x];
                    adj2[y].add(i);
                    while(x%y==0)
                        x/=y;
                }
            }
            if(max1==1)
            {
                out.println("0");
                return;
            }              
            for(int i=1;i<n;i++)
            {
                x=in.nextInt();
                y=in.nextInt();
                adj1[x].add(y);
                adj1[y].add(x);
            }
            for(int i=2;i<=200000;i++)
                check(i);
            out.print(max);
        }
    }
    /*static class OutputWriter
    {
        private final PrintWriter writer;

        public OutputWriter(OutputStream outputStream)
        {
            writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
        }

        public OutputWriter(Writer writer)
        {
            this.writer = new PrintWriter(writer);
        }

        public void print(Object... objects)
        {
            for(int i=0;i<objects.length;i++)
            {
                if (i!=0)
                {
                    writer.print(' ');
                }
                writer.print(objects[i]);
            }
        }

        public void println(Object... objects)
        {
            print(objects);
            writer.println();
        }

        public void close()
        {
            writer.close();
        }
    }*/

static class InputReader 
{
    private InputStream stream;
    private byte[] buf = new byte[8192];
    private int curChar, snumChars;
    private SpaceCharFilter filter;
 
    public InputReader(InputStream stream) 
    {
        this.stream = stream;
    }
 
    public int snext() 
    {
        if(snumChars==-1)
            throw new InputMismatchException();
        if(curChar>=snumChars)
        {
            curChar=0;
            try 
            {
                snumChars = stream.read(buf);                
            } 
            catch(IOException e) 
            {
                throw new InputMismatchException();
            }
            if(snumChars<=0)
                return -1;
        }
        return buf[curChar++];
    }
 
    public int nextInt()
    {
        int c = snext();
        while(isSpaceChar(c))
            c=snext();
        int sgn=1;
        if(c=='-')
        {
            sgn = -1;
            c = snext();
        }
        int res=0;
        do
        {
            if(c<'0' || c>'9')
                throw new InputMismatchException();
            res*=10;
            res+=c-'0';
            c=snext();
            }while(!isSpaceChar(c));
        return res * sgn;
    }
 
    public long nextLong()
    {
        int c = snext();
        while(isSpaceChar(c))
            c=snext();
        int sgn=1;
        if(c=='-')
        {
            sgn=-1;
            c=snext();
        }
        long res=0;
        do{
            if (c<'0' || c>'9')
                throw new InputMismatchException();
            res*=10;
            res+=c-'0';
            c=snext();
        }while (!isSpaceChar(c));
        return res * sgn;
    }
 
    public int[] nextIntArray(int n)
    {
        int a[]=new int[n];
        for(int i=0; i<n; i++)
            a[i]=nextInt();
        return a;
    }

    public long[] nextLongArray(int n)
    {
        long a[]=new long[n];
        for(int i=1; i<n; i++)
            a[i]=nextLong();
        return a;
    }
    public String nextString()
    {
        int c=snext();
        while(isSpaceChar(c))
            c=snext();
        StringBuilder res=new StringBuilder();
        do{
            res.appendCodePoint(c);
            c = snext();
        }while (!isSpaceChar(c));
        return res.toString();
    }
 
    public boolean isSpaceChar(int c)
    {
        if(filter != null)
            return filter.isSpaceChar(c);
        return c==' ' || c=='\n' || c=='\r' || c=='\t' || c==-1;
    }
 
    public interface SpaceCharFilter
    {
        public boolean isSpaceChar(int ch);
    }
}
}