Giải bài trực tuyến

Làng của Buba là nơi nổi tiếng với nhiều danh lam thắng cảnh, thu hút hàng nghìn khách du lịch từ nhiều nơi trên thế giới. Làng có  địa điểm du lịch (đánh số từ 1 đến ) và  con đường độ dài 1 nối các cặp địa điểm. Hai địa điểm bất kì đều có thể đi đến nhau qua các con đường này.

Có khách du lịch tại địa điểm 1, những người khách được đánh số từ 1 tới . Người khách thứ nhất muốn thăm tất cả các địa điểm, người khách thứ hai muốn thăm tất cả các địa điểm chia hết cho 2, người khách thứ ba muốn thăm tất cả các địa điểm chia hết cho 3, … Cụ thể là người khách thứ  muốn thăm tất cả các địa điểm chia hết cho .

Yêu cầu: Công ty du lịch muốn lập hành trình cho từng du khách bắt đầu từ địa điểm 1 đi thăm các địa điểm khác rồi quay trở về địa điểm 1 sao cho mỗi du khách được đi qua tất cả các địa điểm anh ta muốn thăm (hành trình có thể qua những địa điểm khác nữa). Bạn cần cho biết độ dài hành trình ngắn nhất của mỗi du khách thỏa mãn yêu cầu trên.

Ví dụ

Giải thích về hành trình vài du khách

Du khách 1 đi theo hành trình  

Du khách 2 và 4 đi theo hành trình

Ít nhất 40% số điểm ứng với các test có N <= 100

Input

• Dòng 1: Chứa số nguyên dương N <= 10^5.
• N dòng tiếp theo, mỗi dòng gồm hai số nguyên u, v cách nhau ít nhất một dấu cách mô tả một con đường nối địa điểm  tới địa điểm .

Output

Ghi ra file văn bản   dòng, dòng thứ  ghi một số nguyên duy nhất là độ dài quãng đường ngắn nhất mà du khách thứ phải đi

Example

Input:
5
1 2
1 3
4 2
5 2

Output:
8
4
2
4
4