给定一个 $n \times n$ 的网格,其中每个单元格要么是黑色(0),要么是白色(1)。
计算满足以下条件的矩形区域的数量:区域内的所有白色单元格都可以被若干个互不重叠的 $2 \times 2$ 正方形完全覆盖,且没有任何黑色单元格被覆盖。每个 $2 \times 2$ 正方形必须完全位于该区域内,且由四个白色单元格组成。
输入格式
第一行包含一个正整数 $n$,表示网格的大小($1 \le n \le 300$)。
接下来的 $n$ 行,每行包含一个长度为 $n$ 的字符串,由数字 ‘0’ 和 ‘1’ 组成。这些行表示网格的各行。
输出格式
输出一个整数:满足条件的矩形区域的数量。
样例
输入 1
4 0110 0110 1111 1111
输出 1
17
说明
请注意,不包含任何白色单元格的区域也被视为有效的区域。