Thầy Minh mới đấu thầu một khu du lịch rộng lớn tại Hạ Long. Bản đồ vùng đất là một lưới ô vuông ~N~*~N~ được chia làm lưới ô vuông đơn vị, các hàng của lưới được đánh số từ 1 tới ~N~ từ trên xuống, và các cột của lưới được đánh số từ 1 tới N từ trái qua phải. Ô nằm trên giao của hàng i và cột j được gọi là ô (i, j) và có độ cao là ~A_{ij}~ Thầy Minh muốn mua một robot để đi lại trên vùng đất này. Robot loại D thì có khả năng di chuyển giữa 2 ô kề cạnh nếu như chênh lệch độ cao giữa 2 ô đúng bằng D.

Hãy giúp thầy Minh chọn loại robot để có thể đặt xe vào một ô trên bảng sao cho từ ô đó đi được tới nhiều ô khác nhất.

Input

• Dòng 1 chứa số nguyên dương ~N \leq 1000~
• N dòng tiếp theo, dòng thứ i chứa N số nguyên không âm, số thứ j là ~A_{ij}~ ≤ ~10^{6}~ .

Các số trên một dòng của file input được ghi cách nhau bởi dấu cách.

Output

• Ghi ra một số nguyên duy nhất là số ô mà robot có thể đi tới được theo phương án chọn robot và chọn ô xuất phát của bạn (tính cả ô xuất phát).

Sample Input

5
0 3 6 3 0
3 7 0 7 3
0 0 9 0 6
3 7 0 7 9
0 3 6 3 6

Sample Output

16