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

Input 1

2
1 1
1 1

Output 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 ### 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

55

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

112