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
// package CodeForces;

import java.io.BufferedOutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.HashMap;
import java.util.InputMismatchException;
import java.util.LinkedList;

public class EducationalRound58D {

	public static int[] lpf;
	public static final int max = (int)2e5 + 10;
	
	public static void makeLPF() {
		lpf = new int[max];
		lpf[1] = 1;
		for(long i = 2; i < max; i++) {
			if(lpf[(int)i] == 0) {
				lpf[(int)i] = (int)i;
				for(long j = i * i; j < max; j += i) {
					if(lpf[(int)j] == 0) {
						lpf[(int)j] = (int)i;
					}
				}
			}
		}
	}
	
	public static HashMap<Integer, Integer> factorMe(int number) {
		HashMap<Integer, Integer> distincts  = new HashMap<Integer, Integer>();
		while(number != 1) {
			distincts.put(lpf[number], 1);
			number /= lpf[number];
		}
		return distincts;
	}
	
	public static LinkedList<Integer>[] adj;
	public static int[] values;
	public static int ans = 0;
	
	public static HashMap<Integer, Integer> dfs(int current, int parent) {
		HashMap<Integer, Integer> toReturn = factorMe(values[current]);
		HashMap<Integer, Pair> forAns = new HashMap<>();
		for(Integer x : toReturn.keySet()) {
			forAns.put(x, new Pair(0));
		}
		for(Integer x : adj[current]) {
			if(x != parent) {
				HashMap<Integer, Integer> child = dfs(x, current);
				for(Integer y : child.keySet()) {
					if(forAns.containsKey(y)) {
						int childvalue = child.get(y);
						forAns.get(y).update(childvalue);
						if(toReturn.get(y) <= childvalue) {
							toReturn.put(y, childvalue + 1);
						}
					}
				}
			}
		}
		for(Pair x : forAns.values()) {
			ans = Integer.max(x.first + x.second + 1, ans);
		}
		return toReturn;
	}
	
	public static void solve() {
		int n = s.nextInt();
		values = s.nextIntArray(n);
		makeLPF();
		adj = new LinkedList[n];
		for(int i = 0; i < n; i++) {
			adj[i] = new LinkedList<Integer>();
		}
		for(int i = 0; i < n - 1; i++) {
			int u = s.nextInt() - 1;
			int v = s.nextInt() - 1;
			adj[u].add(v);
			adj[v].add(u);
		}
		dfs(0, 0);
		out.println(ans);
	}
	
	public static class Pair {
		int first;
		int second; 
		public Pair(int big) {
			this.first = big;
			this.second = 0;
		}
		public void update(int value) {
			if(value > first) {
				second = first;
				first = value;
			}else if(value > second) {
				second = value;
			}
		}
	}

	public static void main(String[] args) {
		new Thread(null, null, "Thread", 1 << 27) {
			public void run() {
				try {
					out = new PrintWriter(new BufferedOutputStream(System.out));
					s = new FastReader(System.in);
					solve();
					out.close();
				} catch (Exception e) {
					e.printStackTrace();
					System.exit(1);
				}
			}
		}.start();
	}

	public static PrintWriter out;
	public static FastReader s;

	public static class FastReader {

		private InputStream stream;
		private byte[] buf = new byte[4096];
		private int curChar, snumChars;

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

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

		public int nextInt() {
			int c = read();
			while (isSpaceChar(c)) {
				c = read();
			}
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			int number = 0;
			do {
				number *= 10;
				number += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			return number * sgn;
		}

		public long nextLong() {
			int c = read();
			while (isSpaceChar(c)) {
				c = read();
			}
			long sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			long number = 0;
			do {
				number *= 10L;
				number += (long) (c - '0');
				c = read();
			} while (!isSpaceChar(c));
			return number * sgn;
		}

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

		public long[] nextLongArray(int n) {
			long[] arr = new long[n];
			for (int i = 0; i < n; i++) {
				arr[i] = this.nextLong();
			}
			return arr;
		}

		public String next() {
			int c = read();
			while (isSpaceChar(c)) {
				c = read();
			}
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isSpaceChar(c));
			return res.toString();
		}

		public String nextLine() {
			int c = read();
			while (isSpaceChar(c)) {
				c = read();
			}
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isEndofLine(c));
			return res.toString();
		}

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

		public boolean isEndofLine(int c) {
			return c == '\n' || c == '\r' || c == -1;
		}

	}

	
}
