题目描述

题目译自 USACO 2020 Feburary Contest, Platinum Problem 2. Equilateral Triangles

Farmer John 的牧场可以被视作一个 $N\times N$ 的网格。对于网格中的每一个单元格，用 * 表示这个单元格里有一头牛，而 . 表示这个单元格里面没有牛。Farmer John 认为他牧场的美观度正比于这些牛形成的等边三角形数量，其中定义这种等边三角形为三头相互之间的距离相等的牛组成的无序$^{[1]}$三元组。

然而，Farmer John 最近才发现他的坐标全是整数，在这种情况下的欧几里得距离不可能存在这种美观的三元组，因此他选用了曼哈顿距离。形式化地说，$(x_0,~y_0),~(x_1,~y_1)$两点间的曼哈顿距离为 $|x_0-x_1|+|y_0-y_1|$。

给出这个网格，代表牛的位置，请求出无序三元组的数量。

$^{[1]}$ 无序一词由译者根据样例解释补充。

输入格式

第一行一个整数 $N$。

第 $i+1~(1\le i\le N)$ 行包含一个长度为 $N$ 的仅含字符 * 和 . 的字符串。第 $j$ 个字符描述在位置 $(i,j)$ 处有没有牛。

输出格式

输出一个整数表示答案，保证答案在 $32$ 位带符号整数范围内。

3
*..
.*.
*..

1

数据范围与提示

除样例外还有 $14$ 组数据，$N$ 分别为 $50,~$$75,~$$100,~$$125,~$$150,~$$175,~$$200,~$$225,~$$250,~$$275,~$$300,~$$300,~$$300,~$$300$。