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
from collections import deque
import sys
from array import array  # noqa: F401
import typing as Tp  # noqa: F401


def input():
    return sys.stdin.buffer.readline().decode('utf-8')


def get_primes(n: int):
    from itertools import chain
    primes = [2, 3]
    is_prime = (array('b', (0, 0, 1, 1, 0, 1, 0))
                + array('b', (1, 0, 0, 0, 1, 0)) * ((n - 1) // 6))

    for i in chain.from_iterable((range(5, n + 1, 6), range(7, n + 1, 6))):
        if is_prime[i]:
            primes.append(i)
            for j in range(i * 3, n + 1, i * 2):
                is_prime[j] = 0

    return is_prime, primes


def solve(adj, start, p, visited, a):
    dq = deque([start])
    visited[start] = 1
    leaf = start

    while dq:
        leaf = v = dq.popleft()
        for dest in adj[v]:
            if visited[dest] == 0 and (a[dest] % p == 0 if p > 0 else a[dest] == -p):
                visited[dest] = 1
                dq.append(dest)

    dq = deque([(leaf, 1)])
    visited[leaf] = 2

    while dq:
        v, res = dq.popleft()
        for dest in adj[v]:
            if visited[dest] == 1 and (a[dest] % p == 0 if p > 0 else a[dest] == -p):
                visited[dest] = 2
                dq.append((dest, res + 1))

    return res


def main():
    n = int(input())
    a = list(map(int, input().split()))
    adj = [[] for _ in range(n)]

    for u, v in (map(int, input().split()) for _ in range(n - 1)):
        adj[u - 1].append(v - 1)
        adj[v - 1].append(u - 1)

    ans = 0
    _, primes = get_primes(448)

    for p in primes:
        visited = [0] * n
        for i in range(n):
            if visited[i] or a[i] % p:
                continue
            ans = max(ans, solve(adj, i, p, visited, a))

    visited = [0] * n
    for i in range(n):
        if visited[i] or a[i] == 1:
            continue
        ans = max(ans, solve(adj, i, -a[i], visited, a))

    print(ans)


if __name__ == '__main__':
    main()
