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.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.util.LinkedList;
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;
        FastScanner in = new FastScanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        D solver = new D();
        solver.solve(1, in, out);
        out.close();
    }

    static class D {
        boolean[] used;
        List<Integer>[] g;
        int[][] divs;
        int[] a;
        int[][] dp;
        int[][] ans;
        int[] dn;

        private void dfs(int v) {
            int[] max = new int[dn[v]];
            int[] max2 = new int[dn[v]];
            for (int u : g[v]) {
                if (!used[u]) {
                    used[u] = true;
                    dfs(u);
                    for (int d = 0; d < dn[v]; d++) {
                        for (int du = 0; du < dn[u]; du++) {
                            if (divs[v][d] == divs[u][du]) {
                                if (dp[u][du] > max[d]) {
                                    max2[d] = max[d];
                                    max[d] = dp[u][du];
                                } else
                                    max2[d] = Math.max(max2[d], dp[u][du]);
                            }
                        }
                    }
                }
            }
            for (int i = 0; i < dn[v]; i++) {
                dp[v][i] = max[i] + 1;
                ans[v][i] = max[i] + 1 + max2[i];
            }
        }

        public void solve(int testNumber, FastScanner in, PrintWriter out) {
            int n = in.ni();
            a = in.na(n);
            ArrayList<Integer> primes = new ArrayList<>();
            int[] lp = new int[200007];
            IntegerUtils.sieve(200003, primes, lp);

            divs = new int[n][10];

            dn = new int[n];
            for (int i = 0; i < n; i++) {
                int num = a[i];
                while (num > 1) {
                    int div = lp[num];
                    while (num % div == 0) {
                        num /= div;
                    }
                    divs[i][dn[i]++] = div;
                }
            }

            g = new List[n];
            for (int i = 0; i < n; i++) {
                g[i] = new LinkedList<>();
            }
            for (int i = 0; i < n - 1; i++) {
                int v = in.ni() - 1, u = in.ni() - 1;
                g[v].add(u);
                g[u].add(v);
            }
            boolean ans0 = true;
            for (int i = 0; i < n; i++) {
                if (a[i] != 1)
                    ans0 = false;
            }
            if (ans0) {
                out.println(0);
                return;
            }
            dp = new int[n][10];
            ans = new int[n][10];

            used = new boolean[n];
            used[0] = true;
            dfs(0);
            int res = 0;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < 10; j++) {
                    res = Math.max(ans[i][j], res);
                }
            }
            out.println(res);

        }

    }

    static class FastScanner {
        private BufferedReader in;
        private StringTokenizer st;

        public FastScanner(InputStream stream) {
            in = new BufferedReader(new InputStreamReader(stream));
        }

        public String ns() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    String rl = in.readLine();
                    if (rl == null) {
                        return null;
                    }
                    st = new StringTokenizer(rl);
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return st.nextToken();
        }

        public int ni() {
            return Integer.parseInt(ns());
        }

        public int[] na(int n) {
            int[] a = new int[n];
            for (int i = 0; i < n; i++) a[i] = ni();
            return a;
        }

    }

    static class IntegerUtils {
        public static void sieve(int n, ArrayList<Integer> pr, int[] lp) {
            for (int i = 2; i < n + 1; i++) {
                if (lp[i] == 0) {
                    lp[i] = i;
                    pr.add(i);
                }
                int j = 0;
                while (j < pr.size() && pr.get(j) <= lp[i] && i * pr.get(j) <= n) {
                    lp[i * pr.get(j)] = pr.get(j);
                    j++;
                }
            }
        }

    }
}

