Trong một trò chơi, bản đồ đại đương được biểu diễn bằng một bảng ô vuông có kích thước \(𝑛 \times 𝑛\). Các dòng của bảng được đánh số từ \(1\) đến \(𝑛\), từ trên xuống dưới. Các cột của bảng được đánh số từ \(1\) đến \(𝑛\), từ trái sang phải. Ô nằm trên giao của dòng \(𝑖\) và cột \(𝑗\) của bảng gọi là ô \((𝑖,𝑗)\).

Ô \((𝑖,𝑗)\) chứa một số nguyên \(𝑟\) biểu diễn một cơn bão có bán kính là \(𝑟\), bão có tâm bão tại ô \((𝑖,𝑗)\); các ô \((𝑥, 𝑦)\) sẽ bị ảnh hưởng bởi bão tại ô \((𝑖,𝑗)\) khi \(|𝑥 − 𝑖| + |𝑦 − 𝑗| \leq 𝑟\) (khoảng cách Manhattan). Nếu \(𝑟 = 0\) thì tại ô đó không có bão.

Yêu cầu: Đếm số lượng ô không bị ảnh hưởng bão.

Input

• Dòng đầu tiên gồm số nguyên dương \(𝑛\) \((𝑛 \leq 3000)\) mô tả kích thước của bảng;
• \(𝑛\) dòng tiếp theo, mỗi dòng gồm \(𝑛\) số nguyên \(𝑟\) \((0 \leq 𝑟 \leq 𝑛)\) mô tả các cơn bão.

Output

• Một số duy nhất là số lượng ô không bị ảnh hưởng bão.

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(𝑛 \leq 100\);
• Subtask \(2\) (\(20\%\) số điểm): \(𝑟 \leq 20\);
• Subtask \(3\) (\(20\%\) số điểm): Các ô có bão đều có bán kính bằng nhau;
• Subtask \(4\) (\(20\%\) số điểm): Không có ràng buộc gì thêm.

Example

4
0 0 0 0
0 0 0 0
0 0 2 0
0 0 0 0

5