Tại thành phố cây, 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 là 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 nó 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.

Hỏi với tất cả cách tổ chức tour như vậy thì tổng số địa điểm được thăm là bao nhiêu?

Input

Vào từ file TOURIST.INP:

• Dòng đầu chứa số nguyên dương là số đỉnh của đồ thị ~N\ (N \le 10^5)~.
• ~N-1~ dòng tiếp theo thể hiện cạnh của đồ thị.

Output

Ghi ra tệp TOURIST.OUT:

• 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.

Sample Input 1

10
3 4
3 7
1 4
4 6
1 10
8 10
2 8
1 5
4 9

Sample Output 1

55

Giải thích

Chúng ta 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~.