Untitled

#include <bits/stdc++.h>

using namespace std;

#define ll long long

void FIO() {
#ifndef ONLINE_JUDGE
    freopen("../in.txt", "r", stdin);
    freopen("../out.txt", "w", stdout);
#endif
}

struct node {
    ll freq0, freq1, sz;
    ll ans;

    node() {
        freq0 = 0;
        freq1 = 0;
        ans = 0;
        sz = 0;
    }
};

ll n;
const ll N = 2e5 + 15;
vector<vector<ll>> adj(N);
bool isPrime[N];

void sieve() {
    memset(isPrime, true, sizeof(isPrime));
    isPrime[0] = isPrime[1] = false;
    for (ll i = 2; i < N; i++) {
        if (isPrime[i]) {
            for (ll j = i * i; j < N; j += i) {
                isPrime[j] = false;
            }
        }
    }
}

node dfs(ll u, ll p) {
    node ret;
    ret.freq1 = isPrime[u];
    ret.freq0 = !isPrime[u];
    ret.sz = 1;
    for (auto v: adj[u]) {
        if (v == p) continue;
        node child = dfs(v, u);
        ret.sz += child.sz;
        if (isPrime[u]) {
            child.freq1 += child.freq0;
            child.freq0 = 0;
        }
        ret.ans += (child.ans +
                    child.freq0 * 1ll * ret.freq1
                    + child.freq1 * 1ll * ret.freq0 +
                    child.freq1 * 1ll * ret.freq1);
        ret.freq0 += child.freq0;
        ret.freq1 += child.freq1;
    }

    return ret;
}

void solve() {
    cin >> n;
    for (ll i = 1; i < n; ++i) {
        ll u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    cout << dfs(1, 0).ans;
}


signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    FIO();
    sieve();

    ll t = 1;
//    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}