Tourists

Tree City has $n$ tourist attractions, labeled 1 to $n$. The attractions are joined by $n - 1$ bidirectional roads, and a tourist can reach any attraction from any other along those roads.

You sit on the Tree City planning committee. After a long study of tourism, the committee found an unusual habit: tourists love number theory. A tourist who visits the attraction labeled $x$ then visits the attraction labeled $y$ whenever $y > x$ and $y$ is a multiple of $x$. If the two attractions are not joined by a road, the tourist passes through every attraction on the path from $x$ to $y$, including the attractions whose labels are not multiples of $x$. The length of a path is the number of attractions the tourist visits, counting $x$ and $y$ themselves.

Consider this city map.

Its roads join 3 and 4, 3 and 7, 1 and 4, 4 and 6, 1 and 10, 8 and 10, 2 and 8, 1 and 5, 4 and 9. Here are the paths tourists might take, with the length of each.

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

The lengths add up to 4 + 3 + 2 + 2 + 3 + 4 + 3 + 3 + 2 + 5 + 6 + 2 + 3 + 3 + 3 + 4 + 3 = 55.

The committee wants that total for the whole city. Take every pair of attractions $(x, y)$ with $y > x$ and $y$ a multiple of $x$, and compute the sum of the lengths of the paths from $x$ to $y$.

The first line contains an integer $n$, the number of attractions. ($2 \le n \le 200\,000$)

Each of the next $n - 1$ lines contains two space separated integers $i$ and $j$ ($1 \le i < j \le n$), meaning that attraction $i$ and attraction $j$ are joined by a road. The attractions are connected.

Print one integer on a single line: the sum of the lengths of the paths from $x$ to $y$ over every pair of attractions $(x, y)$ with $y > x$ and $y$ a multiple of $x$.