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.*;
import java.util.*;
import static java.lang.Math.*;

public class Main {
    public static void main(String[] args)throws Exception {
        FastReader in = new FastReader(System.in);
        PrintWriter pw = new PrintWriter(System.out);
        pf = primeFactors(N+5);
        set = new MultiTreeSet[N+1];
        for (int i = 0; i <= N; i++) {
            if(isPrime[i]) set[i] = new MultiTreeSet<>();
        }
        n = in.nextInt();
        int from[] = new int[n-1], to[] = new int[n-1];
        a = new int[n+1];
        mark = new boolean[n+1];
        vis = new boolean[n+1];
        for (int i = 1; i <= n; i++) {
            a[i] = in.nextInt();
        }
        for (int i = 0; i < n-1; i++) {
            from[i] = in.nextInt();
            to[i] = in.nextInt();
        }

        g = packU(n+1, from, to);
        Centroid_Decomposition cd = new Centroid_Decomposition(g, 1);
        int centroids[] = cd.centroids;
        for(int u : centroids) {
            mark[u] = true;
            add(u, 1, -1, +1);
            for(int v : g[u]) {
                if(mark[v]) continue;
                add(v, 2, a[u], -1);
                calc(v, 2, a[u]);
                add(v, 2, a[u], +1);
            }
            add(u, 1, -1, -1);
        }

        pw.println(max);

        pw.close();
    }

    static MultiTreeSet<Integer> set[];
    static int n, N = (int)2e5;
    static int g[][], a[], pf[][];
    static boolean mark[], vis[];

    static void add(int u, int d, int gcd, int sign) {
        if(gcd == -1) gcd = a[u];
        else gcd = gcd(gcd, a[u]);
        if(gcd > 1) max = max(max, d);
        for(int f : pf[gcd]) {
            if(sign == -1) set[f].remove(d);
            else set[f].add(d);
        }
        vis[u] = true;
        for(int v : g[u]) {
            if(!vis[v] && !mark[v]) add(v, d+1, gcd, sign);
        }
        vis[u] = false;
    }

    static int max = 0;
    static void calc(int u, int d, int gcd) {
        if(gcd == -1) gcd = a[u];
        else gcd = gcd(gcd, a[u]);
        for(int f : pf[gcd]) {
            if(set[f].size != 0) max = max(max, d + set[f].last() - 1);
        }
        vis[u] = true;
        for(int v : g[u]) {
            if(!vis[v] && !mark[v]) calc(v, d+1, gcd);
        }
        vis[u] = false;
    }

    static int gcd(int p, int q) {
        if (q == 0) return p;
        else return gcd(q, p % q);
    }

    static class Centroid_Decomposition{
        int g[][];
        int [] size, par, centroids;
        int idx = 0;
        boolean [] vis;

        Centroid_Decomposition(int g[][], int root){ // 1-based indexed, root = 1
            this.g = g;
            int n = g.length;
            size = new int[n];
            par = new int[n];
            centroids = new int[n];
            idx = 0;
            vis = new boolean[n];
            calcSize(root, 0);
            decompose(root, 0);
        }

        int calcSize(int u, int p) {
            size[u] = 1;
            for (int v : g[u]) {
                if (v != p) {
                    size[u] += calcSize(v, u);
                }
            }
            return size[u];
        }

        void decompose(int u, int p) {
            int max = 0, v = -1;
            for (int x : g[u]) {
                if (!vis[x] && size[x] > max) {
                    max = size[x];
                    v = x;
                }
            }
            while (max > size[u] / 2) {
                int t = size[v];
                size[v] = size[u];
                size[u] = size[v] - t;
                u = v;
                max = 0;
                for (int x : g[u]) {
                    if (!vis[x] && size[x] > max) {
                        max = size[x];
                        v = x;
                    }
                }
            }
            par[u] = p;
            vis[u] = true;
            centroids[idx++] = u;
            for (int x : g[u]) {
                if (!vis[x]) {
                    decompose(x, u);
                }
            }
        }
    }

    static int[][] packU(int n, int[] from, int[] to) {
        int[][] g = new int[n][];
        int[] p = new int[n];
        for (int f : from)
            p[f]++;
        for (int t : to)
            p[t]++;
        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 int[][] primeFactors(int n){
        sieve(n+1);
        int idx[] = new int[n+1];
        for(int i = 1; i <= n; i++){
            for(int j = i; isPrime[i] && j <= n; j+=i){
                idx[j]++;
            }
        }
        int factors[][] = new int[n+1][];
        factors[0] = new int[0];
        for(int i = 1; i <= n; i++){
            factors[i] = new int[idx[i]];
            idx[i] = 0;
        }

        for(int i = 1; i <= n; i++){
            for(int j = i; isPrime[i] &&j <= n; j+=i){
                factors[j][idx[j]++] = i;
            }
        }
        for(int i = 1; i <= n; i++){
            factors[i] = Arrays.copyOf(factors[i], idx[i]);
        }
        return factors;
    }

    static boolean isPrime[];
    static void sieve(int n){
        isPrime = new boolean[n+1];
        Arrays.fill(isPrime, true);
        isPrime[0] = isPrime[1] = false;
        for(int i = 4; i <= n; i += 2) isPrime [i] = false;
        for(int i = 3; i*i <= n; i += 2){
            if(isPrime[i]){
                for(int j = i*i; j <= n; j += 2*i)
                    isPrime [j] = false;
            }
        }
    }

    static class MultiTreeSet<T>{
        int size = 0;
        TreeMap<T, Integer> map = new TreeMap<>();
        void add(T x){
            Integer v = map.get(x);
            if(v == null) map.put(x, 1);
            else map.put(x, v+1);
            size++;
        }

        boolean contains(T x) {
            return map.containsKey(x);
        }

        void clear() {
            map.clear();
        }

        void remove(T x){
            size--;
            int v = 0;
            map.put(x, v = map.get(x)-1);
            if(v == 0) map.remove(x);
        }

        T lower(T x){
            return map.lowerKey(x);
        }

        T higher(T x){
            return map.higherKey(x);
        }

        T ceiling(T x){
            return map.ceilingKey(x);
        }

        T last(){
            return map.lastKey();
        }

        T first(){
            return map.firstKey();
        }

        T floor(T x){
            return map.floorKey(x);
        }
        int size(){
            return size;
        }
    }

    static void debug(Object...obj) {
        System.err.println(Arrays.deepToString(obj));
    }

    static class FastReader {
        InputStream is;
        private byte[] inbuf = new byte[1024];
        private int lenbuf = 0, ptrbuf = 0;

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

        public int readByte() {
            if (lenbuf == -1) throw new InputMismatchException();
            if (ptrbuf >= lenbuf) {
                ptrbuf = 0;
                try {
                    lenbuf = is.read(inbuf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (lenbuf <= 0) return -1;
            }
            return inbuf[ptrbuf++];
        }

        public boolean isSpaceChar(int c) {
            return !(c >= 33 && c <= 126);
        }
        private boolean isEndOfLine(int c) {
            return c == '\n' || c == '\r' || c == -1;
        }

        public int skip() {
            int b;
            while ((b = readByte()) != -1 && isSpaceChar(b)) ;
            return b;
        }

        public String next() {
            int b = skip();
            StringBuilder sb = new StringBuilder();
            while (!(isSpaceChar(b))) {
                sb.appendCodePoint(b);
                b = readByte();
            }
            return sb.toString();
        }



        public String nextLine() {
            int c = skip();
            StringBuilder sb = new StringBuilder();
            while (!isEndOfLine(c)){
                sb.appendCodePoint(c);
                c = readByte();
            }
            return sb.toString();
        }

        public int nextInt() {
            int num = 0, b;
            boolean minus = false;
            while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')) ;
            if (b == '-') {
                minus = true;
                b = readByte();
            }
            while (true) {
                if (b >= '0' && b <= '9') {
                    num = (num << 3) + (num << 1) + (b - '0');
                } else {
                    return minus ? -num : num;
                }
                b = readByte();
            }
        }

        public long nextLong() {
            long num = 0;
            int b;
            boolean minus = false;
            while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')) ;
            if (b == '-') {
                minus = true;
                b = readByte();
            }

            while (true) {
                if (b >= '0' && b <= '9') {
                    num = (num << 3) + (num << 1) + (b - '0');
                } else {
                    return minus ? -num : num;
                }
                b = readByte();
            }
        }

        public double nextDouble() {
            return Double.parseDouble(next());
        }

        public char[] next(int n) {
            char[] buf = new char[n];
            int b = skip(), p = 0;
            while (p < n && !(isSpaceChar(b))) {
                buf[p++] = (char) b;
                b = readByte();
            }
            return n == p ? buf : Arrays.copyOf(buf, p);
        }

        public char readChar() {
            return (char) skip();
        }
    }
}