题目描述

灯光设计师正在为舞台安装灯光装置，该灯光装置由一个 $N \times N$ 的光控矩阵组成。矩阵中的每个单元代表一个独立的灯光模块，模块的状态用数字表示：$1$ 表示该模块亮起，$0$ 表示熄灭。为了营造出独特的光影效果，设计师计划在矩阵中选出一个矩形区域，要求如下：

1. 矩形区域必须至少包含两行和两列（即矩形的长和宽都至少为 $2$）。
2. 矩形区域的四个角所对应的灯光模块必须全部亮起（即对应的数字均为 $1$）。
3. 选出的矩形的长、宽必须和灯光装置的长、宽平行。

你的任务是计算，在给定的光控矩阵中，有多少种不同的矩形区域能满足上述要求，从而实现预期的灯光效果。

输入格式

第一行包含一个整数 $N$，表示光控矩阵的大小为 $N \times N$。

接下来 $N$ 行，每行包含一个长度为 $N$ 的字符串，由字符 $0$ 和 $1$ 组成，分别表示对应行中各个灯光模块的状态。

输出格式

输出一个整数，表示满足条件的矩形区域的总数。

样例

3
011
101
111

2

4
1101
1011
1111
1111

19

提示

样例 1 解释：对于本样例，有 $2$ 种符合题意的矩形构造方案：

1. 选择四个角分别为（行 $1$，列 $2$）$=1$、（行 $1$，列 $3$）$=1$、（行 $3$，列 $2$）$=1$、（行 $3$，列 $3$）$=1$，符合要求。
2. 选择四个角分别为（行 $2$，列 $1$）$=1$、（行 $2$，列 $3$）$=1$、（行 $3$，列 $1$）$=1$、（行 $3$，列 $3$）$=1$，符合要求。

其他组合均不满足条件，因此总方案数为 $2$。

数据范围

• 对于 $50\%$ 的数据：$1 \le N \le 100$
• 对于 $100\%$ 的数据：$1 \le N \le 300$