Между Берляндией и Байтландией война!
Берляндские разведчики с помощью военных дронов сделали цифровую фотографию территории Байтландии. Фотография представляет собой прямоугольник размера n × m пикселей. Каждый пиксель либо белого цвета, либо чёрного. Пиксель белого цвета на фотографии обозначается символом '.', а пиксель чёрного цвета — символом '*'.
Известно, что в Байтландии все здания имеют особую форму. На фотографии каждое здание имеет форму чёрного «креста», все четыре луча которого имеют ширину, равную одному пикселю, положительную длину и параллельны сторонам фотографии. Иными словами, каждое здание выглядит как пара перпендикулярных пересекающихся внутренним образом отрезков из звездочек. Каждый отрезок в паре имеет длину не менее трёх и параллелен сторонам фотографии.
Известно, что на фотографии все чёрные пиксели соответствуют зданиям, каждое здание целиком помещается на фотографии, никакие два здания не пересекаются и не касаются (как стороне так и по углу).
Ниже изображены примеры фотографий:
На фотографиях изображены три, четыре и два здания соответственно. Здание является военным объектом, если оно абсолютно симметрично, то есть если длины всех четырех лучей равны между собой. На рисунке выше на левой фотографии два военных объекта, на центральной фотографии четыре военных объекта, а на правой фотографии один военный объект.
Помогите спецслужбам Берляндии определить количество зданий на фотографии, являющихся военными объектами.
В первой строке следуют два целых числа n и m (3 ≤ n, m ≤ 1 000) — размеры фотографии.
В следующих n строках следуют по m символов '.' и '*' — описание территории Байтландии. Если очередной символ равен '.', то соответствующий пиксель белый на фотографии. Если очередной символ равен '*', то соответствующий пиксель чёрный на фотографии.
Гарантируется, что фотография содержит только здания, имеющие описанный выше вид. Каждое знание целиком помещается на фотографию. Никакие два здания не пересекаются и не касаются (как по стороне, так и по углу). Возможно, что на территории Байтландии нет ни одного здания, то есть все пиксели белые.
Выведите количество зданий на фотографии Байтландии, являющихся военными объектами.
9 8
..*.....
..*.....
*****...
..*.....
..*..*..
.....*..
....***.
.....*..
.....*..
1
12 3
.*.
***
.*.
...
.*.
.*.
***
.*.
...
.*.
***
.*.
2
4 4
....
....
....
....
0
В первом примере здание с центром в точке (3, 3) является военным объектом, так как все лучи, исходящие из этой точки имеют одинаковую длину, равную двум пикселям. Здание с центром в точке (7, 6) не является военным объектом, так как два луча, исходящие из этой точки имеют длину один пиксель, а два других — длину два пикселя.
Во втором примере только здания с центрами в точках (2, 2) и (11, 2) являются военными объектами. Здание с центром в точке (7, 2) не является военным объектом, так как три луча, исходящие из этой точки имеют длину один пиксель, а четвёртый луч имеет длину два пикселя.
В третьем примере на фотографии нет ни одного здания, поэтому количество военных объектов равно нулю.
