Given a tree having N nodes numbered from 1 to N, You have to find the number of paths $(u,\;v)$ such that on path from u to v there should not exist any pair of nodes $(a,\;b)$ such that a divides b.

Input Format:
First line consists of a single integer denoting N.
Following $N-1$ lines consists of two space separated integers $u, v$ denoting there is an edge between node numbered u and node numbered v.

Output Format:
Print the required answer.

Constraints:
$1 \le N \le 10^5$
$1 \le u, v \le N$