#include<bits/stdc++.h>
#define ll long long int
using namespace std;
bool prime[100005];
int dp[100005];
ll answer;
bool visited[100005];
vector<int>adjacent[100005];

void dfs1(int u)
{
    visited[u] = true;
    int sum = prime[u] ? 0 : 1;
    for(int i = 0 ; i < adjacent[u].size() ; i++)
    {
        int v = adjacent[u][i];

        if(!visited[v])
        {
            dfs1(v);
            sum += dp[v];
        }
    }

    dp[u] = sum;

    if(prime[u]) dp[u] = 0;
}

void dfs2(int u, int p, int dv)
{
    visited[u] = true;

    if(prime[u])
    {
        vector<ll>pp;
        ll sum = dv;
        pp.push_back(dv);
        for(int i = 0 ; i < adjacent[u].size() ; i++)
        {
            int v = adjacent[u][i];

            if(!visited[v] && v != p)
            {
                dfs2(v, u, 0);
                pp.push_back(dp[v]);
                sum += dp[v];
            }
        }

        ll val = 0;
        for(int i = 0 ; i < pp.size() ; i++)
        {
            val += (sum-pp[i])*pp[i];
        }

        val /= 2;
        answer += val;
        answer += sum;
    }
    else
    {
        for(int i = 0 ; i < adjacent[u].size() ; i++)
        {
            int v = adjacent[u][i];

            if(!visited[v] && v != p)
            {
                dfs2(v, u, dv + dp[u] - dp[v]);
            }
        }
    }
}

void Sieve()
{
    for(int i = 1 ; i <= 100000 ; i++)
    {
        prime[i] = true;
    }

    prime[1] = false;

    for(int i = 2 ; i*i <= 100000 ; i++)
    {
        if(prime[i])
        {
            for(int j = i*i ; j <= 100000 ; j += i)
            {
                prime[j] = false;
            }
        }
    }
}

int main(){

    Sieve();

    int n;
    cin>>n;
    assert(1 <= n && n <= 100000);

    for(int i = 0 ; i < n - 1 ; i++)
    {
        int u,v;
        cin>>u>>v;
      assert(1 <= u && u <= n);
      assert(1 <= v && v <= n);

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

    dfs1(1);
    for(int i = 1 ; i <= n ; i++) visited[i] = false;

    dfs2(1,0,0);

    cout<<answer<<endl;

}

#include <vector>
#include <iostream>

using namespace std;

int countConnections(const vector<vector<int>>& matrix) {
    int m = matrix.size();
    int n = matrix[0].size();
    
    int count = 0;

    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            if (matrix[i][j] == 1) {
                if (i - 1 >= 0 && j - 1 >= 0 && matrix[i - 1][j - 1] == 1) {
                    count++;
                }
                if (i - 1 >= 0 && matrix[i - 1][j] == 1) {
                    count++;
                }
                if (i - 1 >= 0 && j + 1 < n && matrix[i - 1][j + 1] == 1) {
                    count++;
                }
                if (j + 1 < n && matrix[i][j + 1] == 1) {
                    count++;
                }
            }
        }
    }

    return count;
}

def solve(transactions, userHistory):
    preferredRegion, minValue, maxValue, minScore, maxScore, accountLimit = userHistory
    scrutinized = []
    for transaction in transactions:
        _, region, value, score, _ = transaction
        if value <= accountLimit:
            match_score = 0
            if region == preferredRegion:
                match_score += 2
            if minValue <= value < maxValue:
                match_score += 3
            if minScore <= score <= maxScore:
                match_score += 2
            scrutinized.append(match_score)
    scrutinyScore = 0
    n = len(scrutinized)
    for i in range(n):
        for j in range(i + 1, n):
            scrutinyScore += abs(scrutinized[i] - scrutinized[j])
    
    return scrutinyScore

def solve():
    n = int(input())
    a = list(map(int, input().split()))
    from statistics import median as mm
    pos = {}
    for i, v in enumerate(a):
        if v not in pos:
            pos[v] = []
        pos[v].append(i)
    result = []
    for v, indices in pos.items():
        indices.sort()
        m = len(indices)
        mid_index = mm(indices)
        s = sum(a[i] for i in indices)
        result.append((mid_index, s))
    result.sort()
    print([x[1] for x in result])

solve()

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int T = scanner.nextInt();
        while (T-- > 0) {
            int N = scanner.nextInt(); 
            int M = scanner.nextInt(); 
            int K = scanner.nextInt(); 

            Map<String, Integer> rowCount = new HashMap<>();

            for (int i = 0; i < N; i++) {
                StringBuilder rowPattern = new StringBuilder();
                for (int j = 0; j < M; j++) {
                    int val = scanner.nextInt();
                    rowPattern.append(val);
                }
                String pattern = rowPattern.toString();
                rowCount.put(pattern, rowCount.getOrDefault(pattern, 0) + 1);
            }

            int maxEqualRows = 0;
            Set<String> processedPatterns = new HashSet<>();

            for (String pattern : rowCount.keySet()) {
                if (processedPatterns.contains(pattern)) {
                    continue; 
                }

                StringBuilder complementBuilder = new StringBuilder();
                for (int i = 0; i < pattern.length(); i++) {
                    complementBuilder.append(pattern.charAt(i) == '0' ? '1' : '0');
                }
                String complement = complementBuilder.toString();

                int countPattern = rowCount.get(pattern);
                int countComplement = rowCount.getOrDefault(complement, 0);

                int inversionsNeeded = Math.min(countPattern, countComplement);

                if (inversionsNeeded <= K) {
                    int totalRows = countPattern + countComplement;
                    maxEqualRows = Math.max(maxEqualRows, totalRows);
                }

                processedPatterns.add(pattern);
                processedPatterns.add(complement);
            }

            System.out.println(maxEqualRows);
        }

        scanner.close();
    }
}

from collections import defaultdict
def solve(N, M, K, mat):
    rf, irf = defaultdict(int), defaultdict(int)
    for i in range(N):
        r = tuple(mat[i])
        ir = tuple(1 - x for x in mat[i])
        rf[r] += 1
        irf[ir] += 1
    res = 0
    for r, c in rf.items():
        res = max(res, c)
        if K > 0:
            res = max(res, c + min(K, irf[r]))
    return res

#include <vector>
#include <iostream>
using namespace std;
int longestDiagonalSegment(vector<vector<int>>& matrix) {
    int rows = matrix.size();
    int cols = matrix[0].size();
    int longest = 0;
    int dR[] = {-1, 1, -1, 1}; 
    int dC[] = {1, 1, -1, -1};  
    for (int r = 0; r < rows; ++r) {
    for (int c = 0; c < cols; ++c) {
    for (int dir = 0; dir < 4; ++dir) {
    int len = 0;
    int rPos = r, cPos = c;
    int pattern[] = {1, 2, 0, 2, 0, 2, 0};
    int pIdx = 0;
    while (rPos >= 0 && rPos < rows && cPos >= 0 && cPos < cols) {
    if (matrix[rPos][cPos] == pattern[pIdx]) {
        ++len;
        pIdx = (pIdx + 1) % 7; 
        } else {
        break;
        }
        rPos += dR[dir];
        cPos += dC[dir];
        }
                
        longest = max(longest, len);
            }
        }
    }

    return longest;
}