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 math
import sys


def get_primes(n):
    result = set()
    while n % 2 == 0:
        result.add(2)
        n = n / 2

    for i in range(3, int(math.sqrt(n)) + 1, 2):

        while n % i == 0:
            result.add(i)
            n = n / i

    if n > 2:
        result.add(n)
    return list(result)



def calc(w, t, n):
    stack = []
    stack.append((t[0], dict([(p, [0]) for p in get_primes(w[0])])))
    max_length = 0
    visited = [False] * n
    visited[0] = True
    while stack:
        if stack[-1][0]:
            nxt = stack[-1][0][-1]
            stack[-1][0].pop()
            if visited[nxt]:
                continue
            else:
                visited[nxt] = True
            stack.append((t[nxt], dict([(p, [0]) for p in get_primes(w[nxt])])))
        else:
            last = stack[-1][1]
            stack.pop()
            if last:
                max_length = max(max_length, 1 + max([sum(v) for _, v in last.items()]))
            if stack:
                for k, v in last.items():
                    if k in stack[-1][1].keys():
                        stack[-1][1][k].append(max(v) + 1)
                        stack[-1][1][k].sort(reverse=True)
                        if len(stack[-1][1][k]) > 2:
                            del stack[-1][1][k][-1]
    return max_length


# if __name__ == '__main__':
#     print(primeFactors(100))

if __name__ == '__main__':
    n = int(input())
    weights = list(map(int, input().split()))
    lines = sys.stdin.readlines()
    tree = [[] for _ in range(n)]
    for line in lines:
        x, y = map(int, line.split())
        tree[x - 1].append(y - 1)
        tree[y - 1].append(x - 1)

    print(calc(weights, tree, n))
