Roundup

A country is at war again, and the enemy's last remaining unit is hiding somewhere in a forest. You must plan a roundup to surround it.

You are given a map of the forest as an $n \times n$ grid. Each cell is either a swamp or firm ground. A swamp cell is marked 0, and firm ground is marked 1. Troops can be stationed only on firm ground (1), never on a swamp (0). Troops can reach any non-swamp cell (for example, by helicopter), so the passable cells need not be connected.

By military law, to surround the enemy the troops must be arranged to form the perimeter (border) of an axis-aligned square whose side length is at least 2. In other words, one placement is an axis-aligned square, placed on the grid, all of whose border cells (its top row, bottom row, left column, and right column) are 1. The interior cells of the square may be swamp; only the border cells must be 1.

Because you do not know exactly where the enemy is, you want to count how many ways such a square perimeter can be placed. Two placements are different if they differ in position or in size. Count, over all square side lengths $s \geq 2$, the number of squares whose border cells are all 1.

The first line contains an integer $n$ ($1 \leq n \leq 2000$), the side length of the map. The next $n$ lines follow; the $i$-th of them contains $n$ characters $t_{i,1}, t_{i,2}, \ldots, t_{i,n}$ with no separators, each 0 or 1. If $t_{i,j} = 0$, the cell in row $i$, column $j$ is a swamp; if $t_{i,j} = 1$, it is firm ground.

Print a single integer: the number of ways to place the troops, that is, the number of squares of side length at least 2 whose border cells are all 1.

For the sample test case, the valid placements are the following (rows and columns are numbered from 1). Each square is given by the coordinates of its top-left corner and its side length.

• top-left $(3, 3)$, side length $4$
• top-left $(1, 3)$, side length $3$
• top-left $(3, 2)$, $(3, 3)$, and $(5, 5)$, each of side length $2$

This gives $1 + 1 + 3 = 5$ placements. The side-$4$ square has swamp cells inside it, but because all of its border cells are 1, it is counted as valid.