Methodical Rocket

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 some moves may go off the grid.

Windra's evil twin, Bindra, plots to kill Windra by setting him on a path that goes off the grid. Bindra would like to know how many paths go off the grid.

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 representing the number of paths off the grid.

Constraints

• $1 \leq n \leq 50$
• $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

2
1 1
1 1

6

Explanation 1

There are the following paths:

• Down, down
• Down, right, down
• Down, right, right
• Right, down, down
• Right, down, right
• Right, right

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

59

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

142