Troy 喜欢三角形。他特别喜欢数三角形。他有一个 $N \times N$ 的网格，由 . 或 # 字符组成。请帮助他计算网格中仅由 # 字符组成的三角形数量。

三角形的形状如 #，

 #
###

，

  #
 ###
#####

等。

更正式地，对于某个正整数 $h$，一个高度为 $h$ 的三角形由 $h$ 行组成。对于 $i = 1, \dots, h$，第 $i$ 行包含 $2i - 1$ 个 # 字符。这些行上下居中对齐，使得它们关于穿过它们中心的垂直线对称。

输入格式

第一行包含一个整数 $N$ ($1 \le N \le 2000$)，表示网格的大小。接下来的 $N$ 行，每行包含 $N$ 个如上所述的字符。

对于占总分 20% 的测试用例，满足 $N \le 50$。

输出格式

输出网格中三角形的数量。

样例

输入样例 1

5
.....
.###.
.###.
#####
.....

输出样例 1

16

说明

样例中共有 11 个高度为 1 的三角形，4 个高度为 2 的三角形，以及 1 个高度为 3 的三角形。