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.OutputStream;
import java.util.Arrays;
import java.util.HashMap;
import java.util.InputMismatchException;
import java.io.IOException;
import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Collections;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        FastReader in = new FastReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskD solver = new TaskD();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskD {
        public void solve(int testNumber, FastReader in, PrintWriter out) {
            Debug debug = new Debug();

            int n = in.nextInt();
            int[] a = in.nextIntArray(n);
            int[] lpf = NT.enumLowestPrimeFactors(200_000 + 100);

            List<Integer>[] g = new List[n];
            Map<Integer, Integer>[] divDepth = new HashMap[n];
            for (int i = 0; i < n; ++i) {
                divDepth[i] = new HashMap<>();
                g[i] = new ArrayList<>();
            }
            for (int i = 0; i < n - 1; ++i) {
                int u = in.nextInt() - 1;
                int v = in.nextInt() - 1;
                g[u].add(v);
                g[v].add(u);
            }

            int[][] pars = GraphUtils.parents3(g, 0);
            int[] par = pars[0], ord = pars[1], depth = pars[2];

            int ans = 0;
            for (int i = n - 1; i >= 0; --i) {
                int cur = ord[i];
                int parent = par[cur];

                HashMap<Integer, ArrayList<Integer>> child = new HashMap<>();
                for (Integer next : g[cur]) {
                    if (next == parent) continue;
                    for (Map.Entry<Integer, Integer> entry : divDepth[next].entrySet()) {
                        int key = entry.getKey();
                        int value = entry.getValue();

                        ArrayList<Integer> list = child.get(key);
                        if (list == null) list = new ArrayList<>();
                        list.add(value);
                        child.put(key, list);
                    }
                }

                int[] divs = getAllDivs(lpf, a[cur]);
//            debug.tr(cur, a[cur]);
                for (int div : divs) {
                    ArrayList<Integer> list = child.get(div);
                    if (list == null) list = new ArrayList<>();
                    list.add(0);
                    list.add(0);
                    Collections.sort(list);
                    int max = list.get(list.size() - 1);
                    divDepth[cur].put(div, max + 1);
                    int m1 = list.get(list.size() - 1);
                    int m2 = list.get(list.size() - 2);
                    ans = Math.max(ans, 1 + m1 + m2);
                }
            }
            out.println(ans);
        }

        private int[] getAllDivs(int[] lpf, int n) {
            int[] div = new int[20];
            int ptr = 0;

            while (lpf[n] != 0) {
                int p = lpf[n];
                div[ptr++] = p;

                while (n % p == 0) n /= p;
            }
            return Arrays.copyOf(div, ptr);
        }

    }

    static class Debug {
        PrintWriter out;
        boolean oj;
        boolean system;
        long timeBegin;
        Runtime runtime;

        public Debug(PrintWriter out) {
            oj = System.getProperty("ONLINE_JUDGE") != null;
            this.out = out;
            this.timeBegin = System.currentTimeMillis();
            this.runtime = Runtime.getRuntime();
        }

        public Debug() {
            system = true;
            oj = System.getProperty("ONLINE_JUDGE") != null;
            OutputStream outputStream = System.out;
            this.out = new PrintWriter(outputStream);
            this.timeBegin = System.currentTimeMillis();
            this.runtime = Runtime.getRuntime();
        }

    }

    static class GraphUtils {
        public static int[][] parents3(List<Integer>[] g, int root) {
            int n = g.length;
            int[] par = new int[n];
            ArrayUtils.fill(par, -1);

            int[] depth = new int[n];
            depth[0] = 0;

            int[] q = new int[n];
            q[0] = root;
            for (int p = 0, r = 1; p < r; p++) {
                int cur = q[p];
                for (int nex : g[cur]) {
                    if (par[cur] != nex) {
                        q[r++] = nex;
                        par[nex] = cur;
                        depth[nex] = depth[cur] + 1;
                    }
                }
            }
            return new int[][]{par, q, depth};
        }

    }

    static class FastReader {
        private InputStream stream;
        private byte[] buf = new byte[8192];
        private int curChar;
        private int pnumChars;

        public FastReader(InputStream stream) {
            this.stream = stream;
        }

        private int pread() {
            if (pnumChars == -1) {
                throw new InputMismatchException();
            }
            if (curChar >= pnumChars) {
                curChar = 0;
                try {
                    pnumChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (pnumChars <= 0) {
                    return -1;
                }
            }
            return buf[curChar++];
        }

        public int nextInt() {
            int c = pread();
            while (isSpaceChar(c))
                c = pread();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = pread();
            }
            int res = 0;
            do {
                if (c == ',') {
                    c = pread();
                }
                if (c < '0' || c > '9') {
                    throw new InputMismatchException();
                }
                res *= 10;
                res += c - '0';
                c = pread();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public int[] nextIntArray(int n) {
            int[] array = new int[n];
            for (int i = 0; i < n; i++) {
                array[i] = nextInt();
            }
            return array;
        }

        private boolean isSpaceChar(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

    }

    static class NT {
        public static int[] enumLowestPrimeFactors(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;
        }

    }

    static class ArrayUtils {
        public static void fill(int[] array, int value) {
            Arrays.fill(array, value);
        }

    }
}

