포위 작전

어떤 나라가 다시 전쟁에 돌입했고, 적의 마지막 부대 하나가 숲 어딘가에 숨어 있습니다. 여러분은 이 부대를 포위하는 작전을 계획해야 합니다.

숲의 지도는 $n \times n$ 크기의 격자로 주어집니다. 각 칸은 늪이거나, 늪이 아닌 단단한 땅입니다. 늪인 칸은 0, 늪이 아닌 칸은 1로 표시됩니다. 병력은 늪이 아닌 칸(1)에만 배치할 수 있고, 늪(0)에는 배치할 수 없습니다. 병력은 (예를 들어 헬리콥터를 이용해) 늪이 아닌 어떤 칸에도 도달할 수 있으므로, 배치할 칸들이 서로 연결되어 있을 필요는 없습니다.

군율에 따르면 적을 포위할 때 병력은 한 변의 길이가 2 이상인 정사각형의 둘레(테두리)를 이루도록 배치해야 합니다. 즉 하나의 배치란, 격자 위에 놓인 축에 평행한 정사각형 중에서 그 둘레에 해당하는 칸들(맨 윗줄, 맨 아랫줄, 맨 왼쪽 열, 맨 오른쪽 열)이 모두 1인 것을 말합니다. 정사각형의 내부 칸은 늪이어도 상관없으며, 오직 둘레 칸만 모두 1이면 됩니다.

적이 정확히 어디 있는지 모르기 때문에, 이런 정사각형 둘레를 배치할 수 있는 방법이 모두 몇 가지인지 세려고 합니다. 위치나 크기가 다르면 서로 다른 방법으로 봅니다. 한 변의 길이가 $s \geq 2$인 모든 정사각형에 대해, 둘레 칸이 전부 1인 것의 개수를 구하세요.

첫째 줄에 지도의 한 변의 길이를 나타내는 정수 $n$ ($1 \leq n \leq 2000$)이 주어집니다. 이어서 $n$개의 줄이 주어지며, $i$번째 줄에는 $n$개의 문자 $t_{i,1}, t_{i,2}, \ldots, t_{i,n}$이 공백 없이 이어집니다. 각 문자는 0 또는 1입니다. $t_{i,j} = 0$이면 $i$행 $j$열 칸이 늪이고, $t_{i,j} = 1$이면 늪이 아닙니다.

첫째 줄에 정수 하나를 출력합니다. 이는 병력을 배치할 수 있는 방법의 수, 즉 한 변의 길이가 2 이상이면서 둘레 칸이 모두 1인 정사각형의 개수입니다.

샘플 테스트 케이스에서 유효한 배치는 다음과 같습니다(행과 열은 1부터 셉니다). 각 정사각형은 왼쪽 위 꼭짓점의 좌표와 한 변의 길이로 나타냅니다.

• 왼쪽 위 $(3, 3)$, 한 변의 길이 $4$
• 왼쪽 위 $(1, 3)$, 한 변의 길이 $3$
• 왼쪽 위 $(3, 2)$, $(3, 3)$, $(5, 5)$, 각각 한 변의 길이 $2$

따라서 $1 + 1 + 3 = 5$가지입니다. 한 변의 길이가 $4$인 정사각형 내부에는 늪이 있지만, 둘레 칸이 모두 1이므로 유효한 배치로 셉니다.