#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
using ll = long long;
#define pb emplace_back
#define X first
#define Y second
#define AI(i) begin(i), end(i)
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true);}
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true);}
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T l, T r) { cerr << *l++ << " \n"[l==r]; }
#else
#define DE(...) 0
#define debug(...) 0
#endif

const int MAX_N = 300010;
int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);

	auto solve = [&]() {
		int n;
		cin >> n;

		vector<int> a(n);
		for (int i = 0; i < n; i++) {
			cin >> a[i];
		}

		constexpr int N = 1e6;
		vector<int> minp(N + 1), primes;
		for (int i = 2; i <= N; i++) {
			if (minp[i] == 0) {
				primes.push_back(i);
				minp[i] = i;
			}
			for (int p : primes) {
				if (p > N / i) {
					break;
				}
				minp[p * i] = p;
				if (i % p == 0) {
					break;
				}
			}
		}

		vector<vector<pair<int, int>>> qs(N + 1);

		for (int i = 0; i < n - 1; i++) {
			int u, v;
			cin >> u >> v;
			u--, v--;
			int g = gcd(a[u], a[v]);
			while (g > 1) {
				int p = minp[g];
				while (g % p == 0) {
					g /= p;
				}
				DE(p, u, v);
				qs[p].emplace_back(u, v);
			}
		}

		vector<int> sz(n, 1), fa(n);
		iota(fa.begin(), fa.end(), 0);

		function<int(int)> find = [&](int u) {
			return u == fa[u] ? u : find(fa[u]);
		};
		auto join = [&](int u, int v) {
			u = find(u), v = find(v);
			if (u != v) {
				if (sz[u] < sz[v]) {
				   swap(u, v);	
				}
				sz[u] += sz[v];
				fa[v] = u;
			}
		};
		auto size = [&](int u) { return sz[find(u)]; };

		int ans = 0;

		for (int i = 2; i <= N; i++) {
			if (minp[i] == i) {
				for (auto [u, v] : qs[i]) {
					join(u, v);
					ans = max(ans, size(u));
				}
				for (auto [u, v] : qs[i]) {
					fa[u] = u;
					fa[v] = v;
					sz[u] = sz[v] = 1;
				}
			}
		}

		cout << ans << '\n';
	};

	solve();
}