D. Flowers
time limit per test
5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Having a nice garden is hard, especially when you are obsessed about the $$$aesthetics$$$. Such is the life of Ionel, who wants to have the prettiest garden he ever could. He also has a quite narrow point of view - in his eyes, flowers are either ugly or pretty - no in-between.

Therefore, to establish how beautiful a garden is, Ionel has patented a beauty coefficient. This coefficient is calculated as the number of squares that a garden has, such that the squares' perimeter is filled solely by beautiful flowers. In order to figure out how pretty his garden is, Ionel has tasked you with finding this coefficient.

Formally, you are given a matrix of size $$$N \times N$$$, where $$$1 \leq N \leq 3 \times 10^3$$$. Each cell of this matrix can either have value $$$0$$$, denoting an non-aesthetically pleasing flower, or value $$$1$$$, referring to a beautiful flower.

It is asked of you to compute the beauty coefficient $$$B$$$ - the number of square submatrices in the matrix whose perimeter consists solely of the value $$$1$$$.

Input

The first line of input contains one integers $$$N$$$, denoting the length of the matrix. Note that $$$1 \leq N \leq 3 \times 10^3$$$.

The next $$$N$$$ lines will contain $$$N$$$ integers $$$a_{ij}$$$, denoting whether the flower at cell $$$(i, j)$$$ is pretty or not. Note that $$$a_{ij}$$$ may either be $$$0$$$ or $$$1$$$.

Output

On a single line, print $$$B$$$, the number of squares in the matrix whose perimeter is surrounded only by $$$1$$$s.

Example
Input
5
1 1 1 0 0
1 0 1 0 0
1 1 1 1 1
0 0 1 0 1
0 0 1 1 1
Output
17