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ứ \(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.

Output

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

Constraints:

• \(1 \le n \le 3000\)

Example

Sample input

5
00010
11111
00110
11001
00010

Sample output

4