L

#include "bits/stdc++.h"
using namespace std;

#define nl "\n"
#define ll long long
#define mod  1'000'000'007
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define sz(v) (int) v.size()

template<typename T = int>
istream &operator>>(istream &in, vector<T> &v) {
    for (auto &x: v) in >> x;
    return in;
}


template<typename T = int>
ostream &operator<<(ostream &out, const vector<T> &v) {
    for (const T &x: v) out << x << " ";
    return out;
}

void Sira() {
    ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout);
#endif
}

vector < vector < int > > adj;
int n;

vector < int > primes , vis;

const int N = 2e5 + 5;
vector < bool > is_prime(N, true);

void Sieve(){
    is_prime[0] = false;
    is_prime[1] = false;
    for(long long i = 2; i * i < N; i++)
        if(is_prime[i])
            for(int j = 2 * i; j < N; j += i)
                is_prime[j] = false;
}

vector < ll > cnt;

int target;

int dfs(int src){
    vis[src] = 1;

    int ans = 0;

//    cout << src << " ---->" << nl;

    for(auto & nxt : adj[src]){
        if(!vis[nxt] and !is_prime[nxt]){
            int temp = 1 + dfs(nxt);
            ans += temp;
//            cout << temp << " " << src << " " << target << nl;

            if(src == target) cnt.push_back(temp);
        }

    }

    return ans;
}


void solve(){
    cin >> n;

    adj.assign(n + 5 , vector < int > ());
    vis.assign(n + 5 , 0);

    for(int i = 0 ; i < n - 1 ; i++){
        int u , v;
        cin >> u >> v;
//        cout << "adj" << " " << u << " " << v << nl;

        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    for(int i = 1 ; i <= n ; i++){
        if(is_prime[i]) primes.push_back(i);
    }

    ll ans = 0 , rem = n - sz(primes) , p = sz(primes);

    ans = rem * p + p * (p - 1) / 2;

    for(int i = 0 ; i < sz(primes) ; i++){
        target = primes[i];
//        cout << primes[i] << nl;
        dfs(primes[i]);
    }

    for(int i = sz(cnt) - 2 ; i >= 0 ; i--){
        cnt[i] += cnt[i + 1];
    }


    for(int i = 1 ; i < sz(cnt) ; i++){
        ll ele = cnt[i - 1] - cnt[i];
        ele *= cnt[i];
        ans += ele;
    }

    cout << ans << nl;

}

int main() {
    Sira();
    int t = 1;
    Sieve();
//    cin >> t;
    while(t--){
        solve();
    }
    return 0;
}