Problem Statement

Windra has an ~n~ by ~n~ grid of positive integers ~a~. Windra starts at the top left (which contains ~a[1][1]~). Windra will then make a series of moves, he has two choices for each move, if he is at coordinate ~(i, j)~ he can:

• Move to coordinate ~(i + a[i][j], j)~
• Move to coordinate ~(i, j + a[i][j])~

Note that the moves are not always possible as they may go off the grid.

Windra is very adamant about taking the shortest path to the bottom right square, determine how many moves it will take him if he does the least number of moves possible.

If it is not possible then output NOT POSSIBLE.

Input Format

Your first line will contain a single integer ~n~. Your next ~n~ lines will contain ~n~ integers each, representing your row of integers in ~a~.

Output Format

You should output a single integer if there is a path from ~(1, 1)~ to ~(n, n)~, representing the number of moves along the shortest path between them. Otherwise, output NOT POSSIBLE.

Constraints

• ~1 \leq n \leq 500~
• ~1 \leq a[i][j] \leq n + 1~ ## Template

n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]

# print your output

Sample Cases

Input 1

2
1 1
1 1

Output 1

2

Explanation 1

The following is a total of two moves:

• Windra starts at (1, 1)
• Windra moves to (1, 2)
• Windra moves to (2, 2) ### Input 2

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

Output 2

4

Explanation 2

The following is four moves:

• Windra starts at (1, 1)
• Windra moves to (1, 3)
• Windra moves to (2, 3)
• Windra moves to (2, 5)
• Windra moves to (5, 5) ### Input 3

5
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 2 2
1 1 1 2 1

Output 3

NOT POSSIBLE

Explanation 3

Notice Windra has to eventually go to either ~(4, 5)~, ~(5, 4)~ or ~(4, 4)~. However, from those squares he cannot get to the ~(5, 5)~ square.