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 ~n)~ và ~n-1~ 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 ~n~. 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ứ ~k~ muốn thăm tất cả các địa điểm chia hết cho ~k~.

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.

Input

• Dòng ~1~: Chứa số nguyên dương ~N \le 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 ~n~ dòng, dòng thứ ~i~ ghi một số nguyên duy nhất là độ dài quãng đường ngắn nhất mà du khách thứ ~i~ phải đi

Giới hạn

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

Sample Input

5
1 2
1 3
4 2
5 2

Sample Output

8
4
2
4
4

Note

• Du khách ~1~ đi theo hành trình: ~1 \rightarrow 3 \rightarrow 1 \rightarrow 2 \rightarrow 4 \rightarrow 2 \rightarrow 5 \rightarrow 2 \rightarrow 1~
• Du khách ~2~ và ~4~ đi theo hành trình: ~1 \rightarrow 2 \rightarrow 4 \rightarrow 2 \rightarrow 1~
• Du khách ~3~ đi theo hành trình: ~1 \rightarrow 3 \rightarrow 1~
• Du khách ~5~ đi theo hành trình: ~1 \rightarrow 2 \rightarrow 5 \rightarrow 2 \rightarrow 1~