题目描述

Farmer John 的农场可以用一个 $N \times N$ 的方阵（$1 \leq N \leq 300$）。对于方阵内的每个格子，如果这个格子有奶牛，就用 * 表示，否则用 . 表示。

FJ 相信他的牧场的美丽程度正比于两两距离相等的奶牛三元组的数量。也就是说，她们组成一个等边三角形。不幸的是，直到最近 FJ 才发现，由于他的奶牛都处在整数坐标位置，如果使用欧几里得距离进行计算，不可能存在美丽的奶牛三元组！于是，FJ 决定改用“曼哈顿”距离。形式化地说，两点 $(x_0,y_0)$ 和 $(x_1,y_1)$ 的曼哈顿距离等于 $|x_0-x_1|+|y_0-y_1|$。

给定表示奶牛位置的方阵，计算等边三角形的数量。

输入格式

第一行一个整数 $N$。

接下来 $N$ 行，每行一个长度为 $N$ 的字符串，第 $i$ 行的第 $j$ 个字符表示位置 $(i,j)$ 上是否有奶牛。

输出格式

输出一个整数，为所求的答案。可以证明答案可以用 32 位有符号整数型存储。

3
*..
.*.
*..

1

提示

样例解释

有三头奶牛，并且她们组成了一个等边三角形，因为每对奶牛之间的曼哈顿距离都等于二。

子任务

• 对于测试点 $T$（$T \in [2,11]$），满足 $N=25T$；
• 对于测试点 $T$（$T \in [12,15]$），满足 $N=300$。