Given a graph as an adjacency matrix, find the shortest path from the first to the last vertex.

Input Specification

$N\le 100$, the number of vertices.
The adjacency matrix - $N$ rows of $N$ numbers.
The first row represents the first vertex, and similarly the last row represents the last vertex.

Output Specification

The distance from the first to the last vertex.

Sample Input

3
0 1 0
0 0 1
0 0 0

Sample Output

2