#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define sz(x) signed(size(x))
#define fi first
#define se second

inline void solve() {
        int n;
        cin >> n;

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

        vector<vector<int>> edges(n + 1);
        for (int i = 1; i < n; ++i) {
                int u, v;
                cin >> u >> v;
                edges[u].emplace_back(v);
                edges[v].emplace_back(u);
        }

        {
                int tmp = a[1];
                for (int i = 2; i <= n; ++i) {
                        tmp = gcd(tmp, a[i]);
                        if (tmp == 1)
                         break;
                }

                if (tmp != 1) {
                        cout << n;
                        return;
                }
        }

        vector<int> sub(n + 1), si(n + 1);
        auto dfs1 = [&](auto&& self, int cur, int par) -> void {
                sub[cur] = a[cur];
                si[cur] = 1;
                for (int nxt : edges[cur]) {
                        if(nxt == par) continue;
                        self(self, nxt, cur);
                        sub[cur] = gcd(sub[cur], sub[nxt]);
                        si[cur] += si[nxt];
                }
                return;
        };

        dfs1(dfs1, 1, 0);

        int ans = 0;
        auto dfs2 = [&](auto&& self, int cur, int par, int pre) -> void {
                vector<pair<int, int>> v;
                for (int nxt : edges[cur]) {
                        if (nxt == par)
                         v.emplace_back(gcd(a[cur], pre), n - si[cur]);
                        else
                         v.emplace_back(gcd(a[cur], sub[nxt]), si[nxt]);
                }

                vector<int> gg(sz(v)), ggg(sz(v) + 1);
                ggg.back() = a[cur];
                gg[0] = v[0].fi;

                for (int i = 1; i < sz(v); ++i)
                        gg[i] = gcd(gg[i - 1], v[i].fi);
                for (int i = sz(v) - 1; i >= 0; --i)
                        ggg[i] = gcd(ggg[i + 1], v[i].fi);

                if (sz(v) == 1)
                        ans = max(ans, (a[cur] != 1 ? 1 : 0));
                else {
                        for (int i = 0; i < sz(v); ++i) {
                         if (i == 0) {
                                if (ggg[1] == 1) continue;
                                ans = max(ans, n - v[i].se);
                         }
                         else if (i == sz(v) - 1) {
                                if (gg[i - 1] == 1) continue;
                                ans = max(ans, n - v[i].se);
                         }
                         else {
                                if (gcd(gg[i - 1], ggg[i + 1]) == 1) continue;
                                ans = max(ans, n - v[i].se);
                         }
                        }
                }

                for (int i = 0; i < sz(edges[cur]); ++i) {
                        if (edges[cur][i] == par) continue;
                        int tmp;
                        if (i == 0)
                         tmp = ggg[i + 1];
                        else if (i == sz(edges[cur]) - 1)
                         tmp = gg[i - 1];
                        else
                         tmp = gcd(gg[i - 1], ggg[i + 1]);

                        self(self, edges[cur][i], cur, tmp);
                }

        };


        dfs2(dfs2, 1, 0, 0);
        cout << ans << '\n';
        return;
}

signed main() {
        cin.tie(0)->sync_with_stdio(0);
        int t = 1;
        while (t--)
                solve();
        return 0;
}