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 static java.lang.Math.*;
public class Main {
    static final long MOD = 1_000_000_007, INF = 1_000_000_000_000_000_000L;
    static final int INf = 1_000_000_000;
    static FastReader reader;
    static PrintWriter writer;
    public static void main(String[] args) {
        Thread t = new Thread(null, new O(), "Integer.MAX_VALUE", 100000000);
        t.start();
    }
    static class O implements Runnable {
        public void run() {
            try {
                magic();
            }
            catch (Exception e) {
                e.printStackTrace();
                System.exit(1);
            }
        }
    }
    static class FastReader {
        final private int BUFFER_SIZE = 1 << 16;
        private DataInputStream din;
        private byte[] buffer;
        private int bufferPointer, bytesRead;

        public FastReader() {
            din = new DataInputStream(System.in);
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public FastReader(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];
            int cnt = 0, c;
            while ((c = read()) != -1) {
                if (c == '\n') break;
                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();
        }
    }
    //variables here
    static int n,val[],u[], v[],mx = 0;
    static ArrayList<Integer> edges_having_weight_divisible_by[] = new ArrayList[200001];
    static ArrayList<Integer> adj[];
    static boolean vis[];
    static void magic() throws IOException{
        reader = new FastReader();
        writer = new PrintWriter(System.out, true);
        int pfs[][] = new int[200001][10];
        int ptr[] = new int[200001];
        for(int i=2;i<=200000;++i) {
            if(ptr[i]==0) {
                for(int j=i;j<=200000;j+=i) {
                    pfs[j][ptr[j]++] = i;
                }
            }
        }
        n = reader.nextInt();
        val = new int[n+1];
        for(int i=1;i<=n;++i) {
            val[i] = reader.nextInt();
        }
        if(n==1) {
            if(val[1]>1) {
                writer.println(1);
            }
            else {
                writer.println(0);
            }
            System.exit(0);
        }
        u = new int[n-1];
        v = new int[n-1];
        vis = new boolean[n+1];
        for(int i=0;i<=200000;++i) {
            edges_having_weight_divisible_by[i] = new ArrayList<>();
        }
        for(int i=0;i<n-1;++i) {
            u[i] = reader.nextInt();
            v[i] = reader.nextInt();
            int uval = val[u[i]];
            int vval = val[v[i]];
            for(int j=0;j<ptr[uval];++j) {
                //writer.print(pfs[uval][j]);
                if(vval%pfs[uval][j]==0) {
                    edges_having_weight_divisible_by[pfs[uval][j]].add(i);
                }
            }
            //writer.println();
        }
        adj = new ArrayList[n+1];
        for(int i=1;i<=n;++i) {
            adj[i] = new ArrayList<>();
        }
        boolean inc[] = new boolean[n+1];
        int vertices[] = new int[n];
        int idx = 0;
        int max = 0;
        for(int i=0;i<=200000;++i) {
            if(!edges_having_weight_divisible_by[i].isEmpty()) {
                for(int e : edges_having_weight_divisible_by[i]) {
                    if(!inc[u[e]]) {
                        vertices[idx++] = u[e];
                        inc[u[e]] = true;
                    }
                    if(!inc[v[e]]) {
                        vertices[idx++] = v[e];
                        inc[v[e]] = true;
                    }
                    adj[u[e]].add(v[e]);
                    adj[v[e]].add(u[e]);
                }
                mx = 0;
                for(int j=0;j<idx;++j) {
                    if(!vis[vertices[j]]) {
                        dfs(vertices[j]);
                        max = max(max, 1+mx);
                    }
                }
                //reset
                idx = 0;
                for(int e : edges_having_weight_divisible_by[i]) {
                    inc[u[e]] = inc[v[e]] = false;
                    adj[u[e]].clear();
                    adj[v[e]].clear();
                    vis[u[e]] = vis[v[e]] = false;
                }
            }
        }
        for(int i=1;i<=n;++i) {
            if(val[i]>1) {
                max = max(max, 1);
            }
        }
        writer.println(max);
    }
    static int dfs(int v) {
        vis[v] = true;
        int mx1 = -1, mx2 = -1;
        for(int e : adj[v]) {
            if(!vis[e]) {
                int d = dfs(e);
                if(d>=mx1) {
                    mx2 = mx1;
                    mx1 = d;
                }
                else if(d>mx2) {
                    mx2 = d;
                }
            }
        }
        mx = max(mx,2+mx1+mx2);
        return 1+mx1;
    }
}