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
/**
 * author: derrick20
 * created: 11/25/20 10:37 PM
 */
import java.io.*;
import java.util.*;
import static java.lang.Math.*;

public class GCDCounting {
    public static void main(String[] args) {
        int MAX = (int) 2e5;
        primeFactors = new ArrayList[MAX + 1];
        Arrays.setAll(primeFactors, i -> new ArrayList<>());
        for (int p = 2; p <= MAX; p++) {
            if (primeFactors[p].size() == 0) {
                for (int value = p; value <= MAX; value += p) {
                    primeFactors[value].add(p);
                }
            }
        }
        /*
        key bug: we only need to consider indvidual primes for the paths, since all
        other non-prime values can be composed of prime paths and are no more inclusive
         */
        FastScanner sc = new FastScanner();
        PrintWriter out = new PrintWriter(System.out);

        int N = sc.nextInt();
        a = sc.nextInts(N);
        dp = new HashMap[N];
        Arrays.setAll(dp, i -> new HashMap<>());
        adjList = new ArrayList[N];
        Arrays.setAll(adjList, i -> new ArrayList<>());
        for (int i = 0; i < N - 1; i++) {
            int u = sc.nextInt() - 1;
            int v = sc.nextInt() - 1;
            adjList[u].add(v);
            adjList[v].add(u);
        }
        solve(0, -1);
//        System.out.println(Arrays.toString(dp));
        out.println(diameter);
        out.close();
    }

    static HashMap<Integer, Integer>[] dp;
    static ArrayList<Integer>[] primeFactors;
    static ArrayList<Integer>[] adjList;
    static int[] a;
    static int diameter;

    static void solve(int node, int par) {
        for (int adj : adjList[node]) {
            if (adj != par) {
                solve(adj, node);
            }
        }
        for (int p : primeFactors[a[node]]) {
            int best = 0;
            int nextBest = 0;
            for (int adj : adjList[node]) {
                if (adj != par) {
                    int amt = dp[adj].getOrDefault(p, 0);
                    if (amt >= best) {
                        nextBest = best;
                        best = amt;
                    } else if (amt > nextBest) {
                        nextBest = amt;
                    }
                }
            }
            dp[node].put(p, 1 + best);
            diameter = max(diameter, 1 + best + nextBest);
        }
    }

    static class FastScanner {
        private int BS = 1 << 16;
        private char NC = (char) 0;
        private byte[] buf = new byte[BS];
        private int bId = 0, size = 0;
        private char c = NC;
        private double cnt = 1;
        private BufferedInputStream in;

        public FastScanner() {
            in = new BufferedInputStream(System.in, BS);
        }

        public FastScanner(String s) {
            try {
                in = new BufferedInputStream(new FileInputStream(new File(s)), BS);
            } catch (Exception e) {
                in = new BufferedInputStream(System.in, BS);
            }
        }

        private char getChar() {
            while (bId == size) {
                try {
                    size = in.read(buf);
                } catch (Exception e) {
                    return NC;
                }
                if (size == -1) return NC;
                bId = 0;
            }
            return (char) buf[bId++];
        }

        public int nextInt() {
            return (int) nextLong();
        }

        public int[] nextInts(int N) {
            int[] res = new int[N];
            for (int i = 0; i < N; i++) {
                res[i] = (int) nextLong();
            }
            return res;
        }

        public long[] nextLongs(int N) {
            long[] res = new long[N];
            for (int i = 0; i < N; i++) {
                res[i] = nextLong();
            }
            return res;
        }

        public long nextLong() {
            cnt = 1;
            boolean neg = false;
            if (c == NC) c = getChar();
            for (; (c < '0' || c > '9'); c = getChar()) {
                if (c == '-') neg = true;
            }
            long res = 0;
            for (; c >= '0' && c <= '9'; c = getChar()) {
                res = (res << 3) + (res << 1) + c - '0';
                cnt *= 10;
            }
            return neg ? -res : res;
        }

        public double nextDouble() {
            double cur = nextLong();
            return c != '.' ? cur : cur + nextLong() / cnt;
        }

        public double[] nextDoubles(int N) {
            double[] res = new double[N];
            for (int i = 0; i < N; i++) {
                res[i] = nextDouble();
            }
            return res;
        }

        public String next() {
            StringBuilder res = new StringBuilder();
            while (c <= 32) c = getChar();
            while (c > 32) {
                res.append(c);
                c = getChar();
            }
            return res.toString();
        }

        public String nextLine() {
            StringBuilder res = new StringBuilder();
            while (c <= 32) c = getChar();
            while (c != '\n') {
                res.append(c);
                c = getChar();
            }
            return res.toString();
        }

        public boolean hasNext() {
            if (c > 32) return true;
            while (true) {
                c = getChar();
                if (c == NC) return false;
                else if (c > 32) return true;
            }
        }
    }
    static void ASSERT(boolean assertion, String message) {
        if (!assertion) throw new AssertionError(message);
    }
    static void ASSERT(boolean assertion) {
        if (!assertion) throw new AssertionError();
    }
}