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.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.io.FilterInputStream;
import java.io.BufferedInputStream;
import java.util.HashMap;
import java.io.InputStream;

/**
 * @author khokharnikunj8
 */

public class Main {
    public static void main(String[] args) {
        new Thread(null, new Runnable() {
            public void run() {
                new Main().solve();
            }
        }, "1", 1 << 26).start();
    }

    void solve() {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        ScanReader in = new ScanReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        DGCDCounting solver = new DGCDCounting();
        solver.solve(1, in, out);
        out.close();
    }

    static class DGCDCounting {
        int[] ai;
        int[][] G;
        int[] lpf;
        HashMap<Integer, Integer>[] max1;
        HashMap<Integer, Integer>[] max2;
        int ans;

        public int[] LPF(int n) {
            int tot = 0;
            int[] lpf = new int[n + 1];
            int u = n + 32;
            double lu = Math.log(u);
            int[] primes = new int[(int) (u / lu + u / lu / lu * 1.5)];
            for (int i = 2; i <= n; i++)
                lpf[i] = i;
            for (int p = 2; p <= n; p++) {
                if (lpf[p] == p)
                    primes[tot++] = p;
                int tmp;
                for (int i = 0; i < tot && primes[i] <= lpf[p] && (tmp = primes[i] * p) <= n; i++) {
                    lpf[tmp] = primes[i];
                }
            }
            return lpf;
        }

        public void dfs(int n, int p) {
            for (int i : G[n]) {
                if (i == p) continue;
                dfs(i, n);
            }
            while (ai[n] != 1) {
                int temp = lpf[ai[n]];
                for (int i : G[n]) {
                    if (max1[i].containsKey(temp)) {

                        int value = max1[i].get(temp);
                        if (max1[n].containsKey(temp)) {
                            if (max1[n].get(temp) <= value) {
                                max2[n].put(temp, max1[n].get(temp));
                                max1[n].put(temp, value);
                            } else {
                                if (!max2[n].containsKey(temp)) {
                                    max2[n].put(temp, value);
                                } else if (max2[n].get(temp) < value) {
                                    max2[n].put(temp, value);
                                }
                            }
                        } else {
                            max1[n].put(temp, value);
                        }


                    }
                }
                if (!max1[n].containsKey(temp)) max1[n].put(temp, 0);
                if (!max2[n].containsKey(temp)) max2[n].put(temp, 0);
                max1[n].put(temp, max1[n].get(temp) + 1);
                max2[n].put(temp, max2[n].get(temp) + 1);
                while (ai[n] % temp == 0) ai[n] /= temp;
            }

            for (int i : max1[n].keySet()) {
                ans = Math.max(ans, max1[n].get(i) + max2[n].get(i) - 1);
            }
        }

        public void solve(int testNumber, ScanReader in, PrintWriter out) {
            int n = in.scanInt();
            ai = new int[n + 1];
            for (int i = 1; i <= n; i++) ai[i] = in.scanInt();
            int[] from = new int[n - 1];
            int[] to = new int[n - 1];
            for (int i = 0; i < n - 1; i++) {
                from[i] = in.scanInt();
                to[i] = in.scanInt();
            }
            max1 = new HashMap[n + 1];
            max2 = new HashMap[n + 1];
            for (int i = 0; i <= n; i++) {
                max1[i] = new HashMap<>();
                max2[i] = new HashMap<>();
            }
            G = CodeHash.packGraph(from, to, n);
            ans = 0;
            lpf = LPF(200005);
            dfs(1, -1);
            out.println(ans);
        }

    }

    static class CodeHash {
        public static int[][] packGraph(int[] from, int[] to, int n) {
            int[][] g = new int[n + 1][];
            int p[] = new int[n + 1];
            for (int i : from) p[i]++;
            for (int i : to) p[i]++;
            for (int i = 0; i <= n; i++) g[i] = new int[p[i]];
            for (int i = 0; i < from.length; i++) {
                g[from[i]][--p[from[i]]] = to[i];
                g[to[i]][--p[to[i]]] = from[i];
            }
            return g;
        }

    }

    static class ScanReader {
        private byte[] buf = new byte[4 * 1024];
        private int index;
        private BufferedInputStream in;
        private int total;

        public ScanReader(InputStream inputStream) {
            in = new BufferedInputStream(inputStream);
        }

        private int scan() {
            if (index >= total) {
                index = 0;
                try {
                    total = in.read(buf);
                } catch (Exception e) {
                    e.printStackTrace();
                }
                if (total <= 0) return -1;
            }
            return buf[index++];
        }

        public int scanInt() {
            int integer = 0;
            int n = scan();
            while (isWhiteSpace(n)) n = scan();
            int neg = 1;
            if (n == '-') {
                neg = -1;
                n = scan();
            }
            while (!isWhiteSpace(n)) {
                if (n >= '0' && n <= '9') {
                    integer *= 10;
                    integer += n - '0';
                    n = scan();
                }
            }
            return neg * integer;
        }

        private boolean isWhiteSpace(int n) {
            if (n == ' ' || n == '\n' || n == '\r' || n == '\t' || n == -1) return true;
            else return false;
        }

    }
}

