An và Bình đang thử nghiệm một mô phỏng sa bàn nông nghiệp thông minh kích thước \(N \times N\), các ô được đánh số ziczac từ \(1\) đến \(N^2\).

Một số ô đất đặc biệt được trang bị:

• Đường ống xả dốc xuống (rắn): Tự động trượt vật thể xuống ô có số hiệu nhỏ hơn.
• Băng chuyền nâng lên (thang): Tự động đưa vật thể lên ô có số hiệu lớn hơn.

Vật thể xuất phát từ ô 1. Mỗi lượt, An gieo một xúc xắc ngẫu nhiên nhận giá trị từ 1 đến 6 để di chuyển. Nếu ô đích có ống xả hoặc băng chuyền, vật thể phải dịch chuyển ngay tới điểm đích của thiết bị đó.

Hãy tìm số lượt gieo xúc xắc tối thiểu để vật thể đi từ ô 1 tới ô \(N^2\).

Định dạng đầu vào

• Dòng đầu chứa số nguyên \(N\) (\(2 \le N \le 20\)).
• \(N\) dòng tiếp theo, mỗi dòng chứa \(N\) số nguyên mô tả giá trị của ô trên sa bàn (bằng -1 nếu là ô thường, hoặc số hiệu ô đích nếu chứa ống xả/băng chuyền).

Định dạng đầu ra

• Một số nguyên duy nhất là số lượt gieo tối thiểu, hoặc -1 nếu không thể tới đích.

Ví dụ

Input:

6
-1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1
-1 35 -1 -1 13 -1
-1 -1 -1 -1 -1 -1
-1 15 -1 -1 -1 -1

Output:

4