Равносторонние треугольники
Пастбище фермера Джона может быть представлено квадратной сеткой n × n, состоящей из позиций (i, j) для всех i, j (1 ≤ i, j ≤ n). Для каждого квадрата сетки соответствующий символ во входных данных равен '*', если в этой позиции находится одна корова, и '.', если в этой позиции нет коровы.
ФД считает, что красота его пастбища прямо пропорциональна количеству троек коров, равноудаленных друг от друга. Другими словами, они образуют равносторонний треугольник. К сожалению, только недавно ФД понял, что, поскольку все его коровы расположены в целочисленных координатах, никакие красивые тройки не могут существовать, если использовать евклидово расстояние! Таким образом, ФД решил перейти на расстояние "Манхэттен". Формально манхэттенское расстояние между двумя позициями (x[0], y[0]) и (x[1], y[1]) равно |x[0] − x[1]| + |y[0] − y[1]|.
По заданной сетке с положением коров вычислите количество равносторонних треугольников.
Входные данные
Первая строка содержит одно целое число n (1 ≤ n ≤ 300). Для каждого i (1 ≤ i ≤ n) строка i + 1 содержит строку длины n, содержащую только символы '*' и '.'. j - й символ указывает, существует ли корова в позиции (i, j) или нет.
Выходные данные
Выведите единственное целое число, содержащее ответ. Известно, что он умещается в 32-битное целое число со знаком.
Пример
Есть три коровы, и они образуют равносторонний треугольник, потому что манхэттенское расстояние между каждой парой коров равно двум.