Giải bài trực tuyến

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(i,j).

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 ≤ 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(i,j) ≤ 10⁶. 

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

Example

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

Output:
16