트리 GCD

정점이 $N$개인 무방향 트리가 주어진다. 각 정점에는 $1$부터 $N$까지의 서로 다른 정수가 번호로 붙어 있다.

$\textrm{dist}(i, j)$는 트리에서 정점 $i$와 정점 $j$를 잇는 최단 경로의 길이이다.

$\sum_{1 \leq i < j \leq N} \gcd(i, j, \textrm{dist}(i, j))$를 구하라. 여기서 $\gcd(a, b, c)$는 $a$, $b$, $c$의 최대공약수이다.

첫째 줄에 정수 $N$이 주어진다. 이후 $N-1$개의 줄에 공백으로 구분된 정수 $u_i$와 $v_i$($1 \leq i \leq N-1$)가 주어지며, 이는 정점 $u_i$와 정점 $v_i$ 사이에 간선이 있다는 뜻이다.

$\sum_{1 \leq i < j \leq N} \gcd(i, j, \textrm{dist}(i, j))$의 값을 출력한다.

$3 \leq N \leq 100\,000$

$1 \leq u_i \leq N$ ($1 \leq i \leq N-1$)

$1 \leq v_i \leq N$ ($1 \leq i \leq N-1$)

주어지는 그래프는 트리이다.