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

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
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 ; 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ệ

Constraints

2 ≤ N ≤ 100
0 ≤ A ≤ 10⁶

Example

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

Output:
11

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