BT mới mua được mảnh đất trên mặt trăng. Bản đồ của vùng đất là một lưới ô vuôngn×n được chia thành các ô vuông đơn vị. Các hàng đánh số \(1, 2, \ldots, n\) từ trên xuống dưới còn các cột đánh số \(1, 2, \ldots, n\) từ trái qua phải. Ô nằm ở giao hàng \(i\), cột \(j\) ký hiệu là \((i,j)\) và có độ cao \(a_{iij}\).
BT muốn mua một robot tự hành để đi lại trên vùng đất này. Robot loại \(D\) có khả năng di chuyển giữa hai ô nếu chênh lệch độ cao giữa chúng đúng bằng \(D\).
Hãy giúp BT chọn một loại robot để có thể đắt xe vào một ô nào đó trên bảng sao cho từ ô đó có thể đi đến được nhiều ô khác nhất.

Input

• Dòng đầu tiên 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}\leq 10^6\).

Output

• Một số nguyên duy nhất là số ô mà robot có thể đến được theo phương án chọn robot và ô xuất phát (tính cả ô xuất phát).

Example

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

16