Counting Manhattan Equilateral Triangles

You are given an N × N grid (1 ≤ N ≤ 300). Each cell of the grid contains either a cow (denoted by *) or is empty (denoted by .). Farmer John believes that the beauty of his farm is proportional to the number of cow triples that form an equilateral triangle with respect to the Manhattan distance.

The Manhattan distance between two points \((x_0, y_0)\) and \((x_1, y_1)\) is defined as \[ |x_0 - x_1| + |y_0 - y_1| \] An equilateral triangle under the Manhattan metric is defined as a triple of cow positions \(A, B, C\) such that

[ |A - B|_1 = |B - C|_1 = |C - A|_1 ]

A key observation is that if the Manhattan distance between two points is \(d\), with \(d = |a|+|b|\), then when \(|a| = |b|\) (and hence \(d = 2k\) for some positive integer \(k\)), the two vectors \((k, k)\) and \((k, -k)\) can be used to form a Manhattan equilateral triangle. For instance, if you have cows at \(A=(x,y)\) and \(B=(x+k, y+k)\), then the triangle can be completed by a cow at either \(A+(k, -k)=(x+k, y-k)\) or \(A+(-k, k)=(x-k, y+k)\), provided those positions are within the grid and contain a cow. Similarly, if \(B-A=(k, -k)\), a corresponding triangle can be completed by using the rotations of that vector.

Your task is to count all such triples of cows that form a Manhattan equilateral triangle.

inputFormat

The first line contains an integer N. The following N lines each contain a string of length N comprising only the characters '*' and '.'.

outputFormat

Output a single integer representing the number of cow triples that form an equilateral triangle under Manhattan distance.

sample

3
.*.
***
.*.

2