Trong kì thi IOI tại Thái Lan vừa qua, sau ~2~ ngày làm bài đầy căng thẳng, Tuệ cùng các thí sinh khác được đi tham quan Thành Cổ (Ancient City), ~1~ địa danh du lịch khá nổi tiếng nơi đây. Thành Cổ ngoài lối vào (được đánh số ~1~) và lối ra (được đánh số ~N~), được chia ra làm ~N-2~ khu vực khác nhau ~(~được đánh số từ ~2~ đến ~N-1)~, mỗi khu vực được xây dựng theo ~1~ lối kiến trúc riêng vô cùng độc đáo. Giữa các khu vực này có thể có các lối đi, được biểu diễn bằng ma trận ~A~.

Hành trình của Tuệ sẽ bắt đầu từ lối vào, tham quan các khu vực trong Thành Cổ và kết thúc ở lối ra. Là ~1~ người yêu thích chụp ảnh, Tuệ chắc chắn sẽ không bỏ qua ~1~ khu vực nào nếu cậu ta có thể đến được nó thông qua các con đường. Tại mỗi địa điểm, nếu còn ít nhất ~1~ khu vực Tuệ có thể đến được nhưng vẫn chưa đến tham quan, cậu ta sẽ chọn khu vực gần nhất so với vị trí hiện tại của cậu ta (có thể di chuyển qua các khu vực đã tham quan rồi hoặc lối vào, lối ra). Nếu có nhiều hơn ~1~ khu vực thỏa yêu cầu, Tuệ sẽ chọn khu vực có số thứ tự nhỏ nhất.

Hãy tính tổng độ dài đường đi trong chuyến tham quan của Tuệ. Luôn đảm bảo có ít nhất ~1~ cách để Tuệ di chuyển từ lối vào đến lối ra.

Input

• Dòng ~1~: số nguyên ~N~ ~( 2 \leq N \leq 100 )~
• Dòng ~2~ ...~N + 1~: dòng thứ ~i + 1~ chứa ~N~ số nguyên ~A_{i, 1} A_{i, 2}~ ...~A_{i, n}~ ~(0 \leq A \leq 10^{6})~; trong đó ~A_{i, j} > 0~ nếu có lối đi và ~A_{i, j} = 0~ nếu không có (với mọi ~i~ khác ~j~, luôn đảm bảo ~A_{i, j}~ = ~A_{j, i}~ và ~A_{i, i} = 0)~

Output

Tổng độ dài chuyến tham quan của Tuệ

Sample Input

5
0 3 2 0 0
3 0 2 4 5
2 2 0 1 0
0 4 1 0 2
0 5 0 2 0

Sample Output

11

Note

Giải thích: Thứ tự các khu vực tham quan là ~3, 4, 2~. Hành trình cụ thể: ~1 \rightarrow 3 \rightarrow 4 \rightarrow 3 \rightarrow 2 \rightarrow 5~.