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.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.*;

public class D {
    public static void main(String[] args) {
        FastIn in = FastIn.wrapSystemIn();
        int n = in.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = in.nextInt();
        }

        boolean all1 = true;
        for (int i = 0; i < n; i++) {
            if (a[i] != 1) {
                all1 = false;
                break;
            }
        }
        if (all1) {
            System.out.println(0);
            return;
        }

        ArrayList<ArrayList<Integer>> g = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            g.add(new ArrayList<>());
        }

        for (int i = 0; i < n - 1; i++) {
            int u = in.nextInt() - 1;
            int v = in.nextInt() - 1;
            g.get(u).add(v);
            g.get(v).add(u);
        }

        int[] f = factorize(200_001);
        ArrayList<ArrayList<Integer>> pToV = new ArrayList<>(200_001);
        for (int i = 0; i < 200_001; i++) {
            pToV.add(new ArrayList<>());
        }
        for (int v = 0; v < n; v++) {
            int k = a[v];
            while (k > 1) {
                pToV.get(f[k]).add(v);
                int fk = f[k];
                while (k % fk == 0) {
                    k /= fk;
                }
            }
        }



        int ans = 0;
        int[] dist = new int[n];
//        ArrayList<ArrayList<Integer>> g2 = new ArrayList<>(n);
//        for (int i = 0; i < n; i++) {
//            g2.add(new ArrayList<>());
//        }
        for (int p = 0; p < pToV.size(); p++) {
            if (pToV.get(p).isEmpty()) {
                continue;
            }

//            for (int i = 0; i < n; i++) {
//                g2.get(i).clear();
//            }
//            for (int v: entry.getValue()) {
//                for (int to: g.get(v)) {
//                    if (to % p == 0) {
//                        g2.get(v).add(to);
//                        g2.get(to).add(v);
//                    }
//                }
//            }

            ArrayList<Integer> vs = pToV.get(p);

            for (int v: vs) {
                dist[v] = -1;
            }
            for (int v: vs) {
                if (dist[v] == -1 ) {
                    dist[v] = 0;
                    int maxDistV = dfs(g, a, dist, -1, v, p);
                    dist[maxDistV] = 0;
                    int diameterV = dfs(g, a, dist, -1, maxDistV, p);
                    ans = Math.max(ans, dist[diameterV]);
                }
            }
        }
        ans++;
        System.out.println(ans);
    }

    private static int dfs(ArrayList<ArrayList<Integer>> g, int[] a, int[] dist, int parent, int from, int prime) {
        int maxDistV = from;
        for (int to : g.get(from)) {
            if (to == parent || a[to] % prime != 0) {
                continue;
            }
            dist[to] = dist[from] + 1;
            int maxToV = dfs(g, a, dist, from, to, prime);
            if (dist[maxToV] > dist[maxDistV]) {
                maxDistV = maxToV;
            }
        }
        return maxDistV;
    }


    private static int[] factorize(int hi) {
        int[] f = new int[hi];
        for (int i = 0; i < f.length; i++) {
            f[i] = i;
        }
        for (int i = 2; i < f.length; i++) {
            if (f[i] != i) {
                continue;
            }
            for (int j = i + i; j < f.length; j += i) {
                if (f[j] == j) {
                    f[j] = i;
                }
            }
        }
        return f;
    }


    static final class FastIn {
        private final BufferedReader bufferedReader;
        private StringTokenizer stringTokenizer;

        static FastIn wrapInputStream(InputStream inputStream) {
            return new FastIn(inputStream);
        }

        static FastIn wrapSystemIn() {
            return wrapInputStream(System.in);
        }

        private FastIn(InputStream inputStream) {
            InputStreamReader inputStreamReader = new InputStreamReader(inputStream);
            this.bufferedReader = new BufferedReader(inputStreamReader);
        }

        int nextInt() {
            return Integer.parseInt(nextToken());
        }

        long nextLong() {
            return Long.parseLong(nextToken());
        }

        String nextString() {
            return nextToken();
        }

        int[] nextIntArrayOfSize(int size) {
            int[] array = new int[size];
            for (int i = 0; i < size; i++) {
                array[i] = nextInt();
            }
            return array;
        }

        long[] nextLongArrayOfSize(int size) {
            long[] array = new long[size];
            for (int i = 0; i < size; i++) {
                array[i] = nextLong();
            }
            return array;
        }

        private String nextToken() {
            try {
                skipUntilNextTokenOrEndOfStream();
                assert hasNextToken();
                return stringTokenizer.nextToken();
            } catch (IOException ioException) {
                throw new RuntimeException(ioException);
            }
        }

        boolean hasNextToken() throws IOException {
            skipUntilNextTokenOrEndOfStream();
            return stringTokenizer.hasMoreTokens();
        }

        private void skipUntilNextTokenOrEndOfStream() throws IOException {
            while (stringTokenizer == null || !stringTokenizer.hasMoreTokens()) {
                String nextLine = bufferedReader.readLine();
                if (nextLine == null) {
                    return;
                }
                this.stringTokenizer = new StringTokenizer(nextLine);
            }
        }
    }
}