Du lịch (tourist.*)

Tại thành phố Alpha có N điểm du lịch hấp dẫn được đánh số từ 1 đến \(n\). Thành phố có \(n - 1\) con đường 2 chiều để nối các điểm du lịch. Thị trưởng thành phố phát hiện ra việc tổ chức các tour đi từ địa điểm \(u\) đến các địa điểm được đánh số là bội của \(u\) sẽ rất thú vị, các tour như vậy thì du khách sẽ được thăm tất cả các địa điểm trên đường đi đơn giữa 2 địa điểm này.

Yêu cầu: Cho biết tổng số địa điểm được thăm với tất cả cách tổ chức tour được xây dựng như trên.

Dữ liệu vào:

• Dòng đầu tiên chứa số nguyên \(n\ (1\ \leq n \leq \ 10^{5})\) là số địa điểm du lịch của thành phố.

• \(n - 1\) dòng tiếp theo, mỗi dòng chứa 2 số nguyên \(u,\ v\) thể hiện đường nối giữa hai thành phố \(u\ \)và \(v\).

Kết quả: Ghi tổng số địa điểm du lịch được thăm với tất cả các tour được xây dựng như trên.

Ví dụ:

Input	Output	Giải thích
10 3 4 3 7 1 4 4 6 1 10 8 10 2 8 1 5 4 9	55	Có tất cả các con đường và số địa điểm có thể thăm được như sau: 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 Do đó, tổng số địa điểm du lịch được thăm sẽ là 55.

Ràng buộc:

• 40% số test với \(1\ \leq \ n\ \leq \ 10^{3}\)

• 60% số test với \(1\ \leq \ n \leq \ 10^{5}\)