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).

For every integer from 1 to 2 ⋅ 10^5 you have to count the number of pairs (x, y) (1 ≤ x ≤ y ≤ n) such that g(x, y) is equal to this number.

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

For every integer i from 1 to 2 ⋅ 10^5 do the following: if there is no pair (x, y) such that x ≤ y and g(x, y) = i, don't output anything. Otherwise output two integers: i and the number of aforementioned pairs. You have to consider the values of i in ascending order.

See the examples for better understanding.

Examples

Input

3
1 2 3
1 2
2 3


Output

1 4
2 1
3 1


Input

6
1 2 4 8 16 32
1 6
6 3
3 4
4 2
6 5


Output

1 6
2 5
4 6
8 1
16 2
32 1


Input

4
9 16 144 6
1 3
2 3
4 3


Output

1 1
2 1
3 1
6 2
9 2
16 2
144 1
#include <bits/stdc++.h>
using namespace std;
const int MaxN = 200000 + 5;
const int MaxA = 200000 + 5;
int N;
int A[MaxN], U[MaxN], V[MaxN];
bool not_prime[MaxA];
int prs[MaxA], cntp, mu[MaxA];
int par[MaxA], siz[MaxA];
bool vis[MaxA];
long long f[MaxA], g[MaxA];
vector<int> E[MaxA];
void Linear_sieve(int n) {
  not_prime[1] = true;
  mu[1] = 1;
  for (int i = 2; i <= n; ++i) {
    if (not_prime[i] == false) {
      prs[++cntp] = i;
      mu[i] = -1;
    }
    for (int j = 1; j <= cntp; ++j) {
      int k = i * prs[j];
      if (k > n) break;
      not_prime[k] = true;
      if (i % prs[j] == 0) break;
      mu[k] = -mu[i];
    }
  }
}
inline int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
void init() {
  scanf("%d", &N);
  for (int i = 1; i <= N; ++i) scanf("%d", &A[i]);
  for (int i = 1; i < N; ++i) scanf("%d %d", &U[i], &V[i]);
  Linear_sieve(200000);
}
int Find(int x) { return x == par[x] ? x : Find(par[x]); }
inline void Merge(int u, int v) {
  int p = Find(u), q = Find(v);
  if (siz[p] < siz[q]) swap(p, q);
  par[q] = p;
  siz[p] += siz[q];
}
void solve() {
  for (int i = 1; i < N; ++i) {
    int u = U[i], v = V[i];
    int n = gcd(A[u], A[v]);
    for (int d = 1; d * d <= n; ++d) {
      if (n % d != 0) continue;
      E[d].push_back(i);
      if (d * d != n) E[n / d].push_back(i);
    }
  }
  for (int i = 1; i <= 200000; ++i) par[i] = i, siz[i] = 1;
  for (int i = 1; i <= 200000; ++i) {
    for (int e : E[i]) {
      int u = U[e], v = V[e];
      Merge(u, v);
    }
    for (int e : E[i]) {
      int p = Find(U[e]);
      if (vis[p] == true) continue;
      vis[p] = true;
      f[i] += 1LL * siz[p] * (siz[p] - 1) / 2;
    }
    for (int e : E[i]) {
      int u = U[e], v = V[e];
      par[u] = u, siz[u] = 1;
      par[v] = v, siz[v] = 1;
      vis[u] = false, vis[v] = false;
    }
  }
  for (int n = 1; n <= 200000; ++n)
    for (int d = 1; n * d <= 200000; ++d) g[n] += mu[d] * f[n * d];
  for (int i = 1; i <= N; ++i) g[A[i]]++;
  for (int i = 1; i <= 200000; ++i)
    if (g[i] != 0) printf("%d %lld\n", i, g[i]);
}
int main() {
  init();
  solve();
  return 0;
}
