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.*;

public class Solution
{
       static class Reader {
        final private int BUFFER_SIZE = 1 << 16;
        private DataInputStream din;
        private byte[] buffer;
        private int bufferPointer, bytesRead;
 
        public Reader()
        {
            din = new DataInputStream(System.in);
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }
 
        public Reader(String file_name) throws IOException
        {
            din = new DataInputStream(
                new FileInputStream(file_name));
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }
 
        public String readLine() throws IOException
        {
            byte[] buf = new byte[64]; // line length
            int cnt = 0, c;
            while ((c = read()) != -1) {
                if (c == '\n') {
                    if (cnt != 0) {
                        break;
                    }
                    else {
                        continue;
                    }
                }
                buf[cnt++] = (byte)c;
            }
            return new String(buf, 0, cnt);
        }
 
        public int nextInt() throws IOException
        {
            int ret = 0;
            byte c = read();
            while (c <= ' ') {
                c = read();
            }
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');
 
            if (neg)
                return -ret;
            return ret;
        }
 
        public long nextLong() throws IOException
        {
            long ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');
            if (neg)
                return -ret;
            return ret;
        }
 
        public double nextDouble() throws IOException
        {
            double ret = 0, div = 1;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
 
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');
 
            if (c == '.') {
                while ((c = read()) >= '0' && c <= '9') {
                    ret += (c - '0') / (div *= 10);
                }
            }
 
            if (neg)
                return -ret;
            return ret;
        }
 
        private void fillBuffer() throws IOException
        {
            bytesRead = din.read(buffer, bufferPointer = 0,
                                 BUFFER_SIZE);
            if (bytesRead == -1)
                buffer[0] = -1;
        }
 
        private byte read() throws IOException
        {
            if (bufferPointer == bytesRead)
                fillBuffer();
            return buffer[bufferPointer++];
        }
 
        public void close() throws IOException
        {
            if (din == null)
                return;
            din.close();
        }
    }
    static int parent(int x , int p[])
    {
           if(p[x] == x)
           return x;
           
           return (p[x] = parent(p[x],p));
    }
    
    static void union(int a , int b , int p[] , int size[])
    {
           a = parent(a,p);
           b = parent(b,p);
           
           if(size[a] < size[b])
           {
                  int temp = a;
                  a = b;
                  b = temp;
           }
           p[b] = a;
           size[a] += size[b];
    }
    
   
  
  static int max(int x)
  {
         for(int j = 30 ; j >= 0 ; j--)
         {
                if((x&(1<<j)) > 0)
                return j;
         }
         return -1;
  }
  static void dfs(int n , LinkedList<Integer> arr[] , int p , int pp[])
  {
         pp[n] = p;
         for(Integer i : arr[n])
         {
                if(i != p)
                {
                       dfs(i,arr,n,pp);
                }
         }
  }
  
  static void dfs2(int n , LinkedList<Integer> arr[] , int p , int w[] , long dp[] , long max[])
  {
         long mx = 0;
         for(Integer i : arr[n])
         {
                if(i != p)
                {
                       dfs2(i,arr,n,w,dp,max);
                       dp[n] += dp[i]+2*w[i];
                       mx = Math.max(mx,w[i]+max[i]);   
                }
         }
         max[n] = mx;
  }
  
 static int getSum( int index , int BITree[])
{
    int sum = 0; // Iniialize result
  
    // index in BITree[] is 1 more than the index in arr[]
   // index = index + 1;
  
    // Traverse ancestors of BITree[index]
    while (index>0)
    {
        // Add current element of BITree to sum
        sum += BITree[index];
  
        // Move index to parent node in getSum View
        index -= index & (-index);
    }
    return sum;
}
  
// Updates a node in Binary Index Tree (BITree) at given index
// in BITree. The given value 'val' is added to BITree[i] and 
// all of its ancestors in tree.
static void updateBIT(int n, int index, int val , int BITree[])
{
    // index in BITree[] is 1 more than the index in arr[]
    //index = index + 1;
  
    // Traverse all ancestors and add 'val'
    while (index <= n)
    {
    // Add 'val' to current node of BI Tree
    BITree[index] += val;
  
    // Update index to that of parent in update View
    index += index & (-index);
    }
}
static int max;
static long inv(int arr[])
{
       int n = arr.length;
       int bit[]  = new int[n+1];
       long ans = 0;
       for(int i = 0 ; i < n; i++)
       {
              updateBIT(n,arr[i],1,bit);
              ans += getSum(n,bit)-getSum(arr[i],bit);
       }
       return ans;
}


static void dfs(int n , int arr[] , LinkedList<Integer> g[] , HashMap<Integer,Integer> map[] , int prime[] , int p)
{
      HashMap<Integer,Integer> mx = new HashMap<Integer,Integer>(); 
       HashMap<Integer,Integer> nextmx = new HashMap<Integer,Integer>(); 
       
       int temp = arr[n];
       for(Integer i : g[n])
       {
              if(i != p)
              {
                     dfs(i,arr,g,map,prime,n);
                     for(Map.Entry entry : map[i].entrySet())
                     {
                            int k = (int)entry.getKey();
                            int v = (int)entry.getValue();
                            
                            if(arr[n]%k == 0)
                            {
                            if(!mx.containsKey(k))
                            mx.put(k,v);
                            
                            else if(!nextmx.containsKey(k))
                            {
                                 if(v >= mx.get(k))
                                 {
                                         nextmx.put(k,mx.get(k));
                                          mx.put(k,v);
                                 }
                                 
                                 else
                                 {
                                        nextmx.put(k,v);
                                 }
                            }
                            
                            
                            else
                            {
                                   if(v >= mx.get(k))
                                   {
                                          nextmx.put(k,mx.get(k));
                                          mx.put(k,v);
                                   }
                                   
                                   else if(v >= nextmx.get(k))
                                   nextmx.put(k,v);
                            }
                     }
              }
       }
}

while(temp > 1)
{
       int x = prime[temp];
       while(temp%x == 0)
       {
              temp = temp/x;
       }
      // int curr = 0;
       if(mx.containsKey(x))
       {
              max = Math.max(max,mx.get(x)+1);
              
              if(nextmx.containsKey(x))
              max = Math.max(max,mx.get(x)+nextmx.get(x)+1);
              
              map[n].put(x,mx.get(x)+1);
       }
       
       else
       {
       map[n].put(x,1);
       max = Math.max(max,1);
       }
}

}
       public static void main(String []args) throws IOException
       {
              Reader sc = new Reader();
              int n = sc.nextInt();
              int arr[] = new int[n];
              int prime[] = new int[200000 + 1];
        for (int i = 0; i <= 200000; i++)
            prime[i] = i;
 
        for (int p = 2; p * p <= 200000; p++)
        {
            // If prime[p] is not changed, then it is a
            // prime
            if (prime[p] == p)
            {
                // Update all multiples of p
                for (int i = p * p; i <= 200000; i += p)
                    prime[i] = p;
            }
        }
        
              HashMap<Integer,Integer> map[] = new HashMap[n];
              LinkedList<Integer> g[] = new LinkedList[n];
              for(int i = 0 ; i < n ;i ++)
              {
                     arr[i] = sc.nextInt();
                     map[i] = new HashMap<Integer,Integer>();
                     g[i] = new LinkedList<Integer>();
              }
              for(int i = 0 ; i < n-1 ; i++)
              {
                     int x = sc.nextInt()-1;
                     int y = sc.nextInt()-1;
                     g[x].add(y);
                     g[y].add(x);
              }
              max = 0;
              dfs(0,arr,g,map,prime,-1);
              
             // System.out.println(prime[4]);
           //  System.out.println(map[2]);
            //  System.out.println(map[1]);
             //  System.out.println(map[0]);
              System.out.println(max);
       }
}