In Tree City, there are $n$ tourist attractions uniquely
labeled $1$ to
$n$. The attractions are
connected by a set of $n1$ bidirectional roads in such a
way that a tourist can get from any attraction to any other
using some path of roads.
You are a member of the Tree City planning committee. After
much research into tourism, your committee has discovered a
very interesting fact about tourists: they LOVE number theory!
A tourist who visits an attraction with label $x$ will then visit another attraction
with label $y$ if
$y>x$ and $y$ is a multiple of $x$. Moreover, if the two attractions
are not directly connected by a road the tourist will
necessarily visit all of the attractions on the path connecting
$x$ and $y$, even if they arenâ€™t multiples of
$x$. The number of
attractions visited includes $x$ and $y$ themselves. Call this the
$length$ of a path.
Consider this city map:
Here are all the paths that tourists might take, with the
lengths for each:
$1 \rightarrow 2=4$,
$1 \rightarrow 3=3$,
$1 \rightarrow 4=2$,
$1 \rightarrow 5=2$,
$1 \rightarrow 6=3$,
$1 \rightarrow 7=4$,
$1 \rightarrow 8=3$,
$1 \rightarrow 9=3$,
$1 \rightarrow 10=2$,
$2 \rightarrow 4=5$,
$2 \rightarrow 6=6$,
$2 \rightarrow 8=2$,
$2 \rightarrow 10=3$,
$3 \rightarrow 6=3$,
$3 \rightarrow 9=3$,
$4 \rightarrow 8=4$,
$5 \rightarrow 10=3$
To take advantage of this phenomenon of tourist behavior,
the committee would like to determine the number of attractions
on paths from an attraction $x$ to an attraction $y$ such that $y>x$ and $y$ is a multiple of $x$. You are to compute the sum of the lengths of all such paths. For the example
above, this is: $4+3+2+2+3+4+3+3+2+5+6+2+3+3+3+4+3=55$.
Input
Each input will consist of a single test case. Note that
your program may be run multiple times on different inputs. The
first line of input will consist of an integer $n$ ($2
\le n \le 200\, 000$) indicating the number of
attractions. Each of the following $n1$ lines will consist of a pair of
spaceseparated integers $i$ and $j$ ($1
\le i<j \le n$), denoting that attraction
$i$ and attraction
$j$ are directly connected
by a road. It is guaranteed that the set of attractions is
connected.
Output
Output a single integer, which is the sum of the lengths of
all paths between two attractions $x$ and $y$ such that $y>x$ and $y$ is a multiple of $x$.
Sample Input 1 
Sample Output 1 
10
3 4
3 7
1 4
4 6
1 10
8 10
2 8
1 5
4 9

55
