Bảng chênh nhỏ

Cho một hình chữ nhật kích thước \(N \times N\), trong đó mỗi ô chứa một số nguyên có giá trị thuộc từ \(0\) đến \(2\). Hãy đếm số lượng hình chữ nhật con (các hình chữ nhật con phải có cạnh song song với các cạnh của bảng) sao cho:

• Hiệu giữa giá trị lớn nhất và giá trị nhỏ nhất trong hình chữ nhật con \(\leq 1\).

Input

• Dòng đầu tiên chứa một số nguyên \(N\) (\(1 \leq N \leq 10^3\)) - kích thước của bảng.
• \(N\) dòng tiếp theo, mỗi dòng chứa \(N\) ký tự thuộc từ '0' đến '2'.

Output

• In ra một số nguyên duy nhất - số lượng hình chữ nhật con thỏa mãn điều kiện.

Example

3
002
110
120

22

4
0001
1102
2222
0000

49

Scoring

• Subtask 1 (11 điểm): \(N \leq 30\).
• Subtask 2 (12 điểm): \(N \leq 70\).
• Subtask 3 (15 điểm): \(N \leq 300\).
• Subtask 4 (62 điểm): Không có ràng buộc gì thêm.