관광객

트리 시티에는 1번부터 $n$번까지 서로 다른 번호가 붙은 관광지가 $n$개 있다. 관광지는 양방향 도로 $n - 1$개로 이어져 있고, 어느 관광지에서 출발해도 도로를 따라 나머지 관광지에 모두 갈 수 있다.

당신은 트리 시티 도시계획 위원회 위원이다. 위원회는 관광 실태를 오래 조사한 끝에 관광객의 독특한 습성을 알아냈다. 관광객은 정수론을 무척 좋아한다. 번호가 $x$인 관광지를 방문한 관광객은 $y > x$이고 $y$가 $x$의 배수인 관광지 $y$를 이어서 방문한다. 두 관광지가 도로로 곧바로 이어져 있지 않으면 관광객은 $x$에서 $y$로 가는 경로 위의 관광지를 하나도 빼놓지 않고 지난다. 번호가 $x$의 배수가 아닌 관광지도 지난다. 경로의 길이는 관광객이 방문한 관광지의 개수이며, $x$와 $y$도 센다.

다음 도시 지도를 보자.

지도의 도로는 3과 4, 3과 7, 1과 4, 4와 6, 1과 10, 8과 10, 2와 8, 1과 5, 4와 9를 잇는다. 관광객이 지날 수 있는 경로와 각 경로의 길이는 다음과 같다.

1 -> 2 = 4, 1 -> 3 = 3, 1 -> 4 = 2, 1 -> 5 = 2, 1 -> 6 = 3, 1 -> 7 = 4,
1 -> 8 = 3, 1 -> 9 = 3, 1 -> 10 = 2, 2 -> 4 = 5, 2 -> 6 = 6, 2 -> 8 = 2,
2 -> 10 = 3, 3 -> 6 = 3, 3 -> 9 = 3, 4 -> 8 = 4, 5 -> 10 = 3

길이를 모두 더하면 4 + 3 + 2 + 2 + 3 + 4 + 3 + 3 + 2 + 5 + 6 + 2 + 3 + 3 + 3 + 4 + 3 = 55이다.

위원회는 도시 전체에 대해 이 합을 알고 싶어 한다. $y > x$이고 $y$가 $x$의 배수인 관광지 쌍 $(x, y)$를 모두 모아, $x$에서 $y$로 가는 경로의 길이를 전부 더한 값을 구하라.

첫째 줄에 관광지의 개수 $n$이 주어진다. ($2 \le n \le 200\,000$)

다음 $n - 1$개 줄에는 공백으로 구분된 두 정수 $i$와 $j$가 주어진다. ($1 \le i < j \le n$) 관광지 $i$와 관광지 $j$가 도로로 곧바로 이어져 있다는 뜻이다. 모든 관광지는 서로 이어져 있다.

$y > x$이고 $y$가 $x$의 배수인 관광지 쌍 $(x, y)$ 전체에 대해, $x$에서 $y$로 가는 경로의 길이를 모두 더한 값을 한 줄에 출력한다.