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 que_b;

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

public class utkarsh {

    InputStream is;
    PrintWriter out;
    
    long mod = (long)(1e9 + 7), inf = (long)(3e18);
    
    class pair {
        int V;  boolean VST;
        pair(int v, boolean vst) {
            V = v;  VST = vst;
        }
    }
    
    ArrayList <Integer> a[];
    ArrayList <pair> d[];
    int val[], ans;
    
    void update(int x, int i) {
        int l = 0, r = d[i].size()-1;
        while(l <= r) {
            int m = (l + r) >> 1;
            if(d[i].get(m).V == x) {
                d[i].get(m).VST = true; return;
            }
            if(d[i].get(m).V > x)   r = m-1;
            else    l = m+1;
        }
    }
    
    int dfs(int s, int pt, int i) {
        update(s, i);
        int m1 = 0, m2 = 0;
        for(int x : a[s]) {
            if(x == pt || val[x] % P[i] != 0) continue;
            int y = dfs(x, s, i);
            if(y > m1) {
                m2 = m1;    m1 = y;
            } else if(y > m2)   m2 = y;
        }
        ans = Math.max(ans, m1 + m2 + 1);
        return m1 + 1;
    }
    
    void solve() {
        SZ = sieve(); //SZ = 17984;
        //out.println(SZ);
        int n = ni();
        val = new int[n];
        a = new ArrayList[n];
        d = new ArrayList[SZ];
        for(int i = 0; i < SZ; i++) d[i] = new ArrayList<>();
        for(int i = 0; i < n; i++) {
            a[i] = new ArrayList<>();
            //int x = (int)(Math.random() * 200000) + 1;
            int x = ni();
            val[i] = x;
            while(S[x] > 1) {
                int u = S[x];
                d[ rev.get(u) ].add(new pair(i, false));
                while(S[x] == u)    x /= u;
            }
        }
        for(int i = 1; i < n; i++) {
            int u = ni()-1, v = ni()-1;
            //int u = (int)(Math.random() * i), v = i;
            a[u].add(v);    a[v].add(u);
        }
        ans = 0;
        for(int i = 0; i < SZ; i++) {
            for(pair p : d[i]) {
                if(!p.VST) {
                    dfs(p.V, -1, i);
                }
            }
        }
        out.println(ans);
    }
    
    //--------- Extra Template -----------
    
    int P[], S[], SZ, NP = (int)2e6 + 10;//15485900;
    boolean isP[];
    HashMap <Integer, Integer> rev;
    
    int sieve() {
        int i, j, n = NP; 
        isP = new boolean[n]; 
        S = new int[n];
        rev = new HashMap<>();
        for(i = 3; i < n; i += 2) {
            isP[i] = true;
            S[i-1] = 2;
            S[i] = i;
        }
        isP[2] = true;
        S[1] = 1;   //(UD)
        for(i = 3; i * i <= n; i += 2) {
            if( !isP[i] )   continue;
            for(j = i * i; j < n; j += i) {
                isP[j] = false;
                if(S[j] == j)   S[j] = i;
            }
        }

        P = new int[n];
        P[0] = 2;   rev.put(2, 0);
        j = 1;
        for(i = 3; i < n; i += 2) {
            if ( isP[i] ) {
                rev.put(i, j);  P[j++] = i;
            }
        }
        P = Arrays.copyOf(P, j);
        return j;
    }

    long mp(long b, long e, long mod) {
        b %= mod;
        long r = 1;
        while(e > 0) {
            if((e & 1) == 1) {
                r *= b; r %= mod;
            }
            b *= b; b %= mod;
            e >>= 1;
        }
        return r;
    }

    //---------- I/O Template ----------
    
    public static void main(String[] args) { new utkarsh().run(); }
    void run() { 
        is = System.in; 
        out = new PrintWriter(System.out);
        solve();
        out.flush();
    }
    
    byte input[] = new byte[1024];
    int len = 0, ptr = 0;
    
    int readByte() { 
        if(ptr >= len) { ptr = 0; 
            try { len = is.read(input); } 
            catch(IOException e) { throw new InputMismatchException(); } 
            if(len <= 0) { return -1; } 
        } return input[ptr++];
    }
    boolean isSpaceChar(int c) { return !( c >= 33 && c <= 126 ); }
    int skip() { 
        int b = readByte(); 
        while(b != -1 && isSpaceChar(b)) { b = readByte(); } 
        return b;
    }
    
    char nc() { return (char)skip(); }
    String ns() { 
        int b = skip(); 
        StringBuilder sb = new StringBuilder(); 
        while(!isSpaceChar(b)) { sb.appendCodePoint(b); b = readByte(); } 
        return sb.toString();
    }
    String nLine() { 
        int b = skip(); 
        StringBuilder sb = new StringBuilder(); 
        while( !(isSpaceChar(b) && b != ' ') ) { sb.appendCodePoint(b); b = readByte(); } 
        return sb.toString();
    }
    int ni() { 
        int n = 0, b = readByte(); 
        boolean minus = false; 
        while(b != -1 && !( (b >= '0' && b <= '9') || b == '-')) { b = readByte(); } 
        if(b == '-') { minus = true; b = readByte(); } 
        if(b == -1) { return -1; }  //no input 
        while(b >= '0' && b <= '9') { n = n * 10 + (b - '0'); b = readByte(); } 
        return minus ? -n : n;
    }
    long nl() { 
        long n = 0L;    int b = readByte(); 
        boolean minus = false; 
        while(b != -1 && !( (b >= '0' && b <= '9') || b == '-')) { b = readByte(); } 
        if(b == '-') { minus = true; b = readByte(); } 
        while(b >= '0' && b <= '9') { n = n * 10 + (b - '0'); b = readByte(); } 
        return minus ? -n : n;
    }

    double nd() { return Double.parseDouble(ns()); }
    float nf() { return Float.parseFloat(ns()); }
    int[] na(int n) { 
        int a[] = new int[n]; 
        for(int i = 0; i < n; i++) { a[i] = ni(); } 
        return a;
    }
    char[] ns(int n) { 
        char c[] = new char[n]; 
        int i, b = skip(); 
        for(i = 0; i < n; i++) { 
            if(isSpaceChar(b)) { break; } 
            c[i] = (char)b; b = readByte(); 
        } return i == n ? c : Arrays.copyOf(c,i);
    }
}