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?

Dữ liệu vào

• Dòng đầu tiên là số địa điểm du lịch \(N\) của thành phố \((1 \le N \le 10^5)\)
• \(N-1\) dòng tiếp theo thể hiện đường nối giữa các thành phố

Dữ liệu ra

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

Input 1

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

Output 1

55