Cho một lưới \(n \times n\) mà mỗi ô vuông có màu đen hoặc màu trắng. Một lưới con được gọi là đẹp nếu chiều cao và chiều rộng của nó ít nhất là hai và tất cả các góc của nó có màu đen. Có bao nhiêu lưới con đẹp trong lưới đã cho.

Input

• Dòng đầu tiên chứa \(n\): kích thước của lưới
• \(n\) dòng tiếp theo, mỗi dòng chứa \(n\) kí tự mô tả lưới: 1 thì ô đó sẽ có màu đen, 0 thì nó sẽ có màu trắng

Constraints

• \(1 \leq n \leq 3000\)

Output

• In ra số lượng lưới con đẹp

Example

5
00010
11111
00110
11001
00010

4