Вот-вот наступит новый год. Рик понял, что ему пора задуматься о покупке традиционных новогодних елок. Но Рику жалко покупать настоящие елки, поэтому он решил найти их в матрице размером \(n \times m\), состоящей из символов «*» и «.».
Для того, чтобы найти все ели, сперва дадим определение ели в матрице. Набор ячеек из матрицы называется елью с высотой \(k\) и вершиной в точке \((x, y)\), если:
- Все ячейки из набора являются символами «*».
- Для всех \(1 \le i \le k\) все ячейки с номером строки \(x+i-1\) и с номерами столбцов в диапазоне \([y - i + 1, y + i - 1]\) должны принадлежать набору. Все остальные ячейки не могут принадлежать набору.
Примеры корректных и некорректных елок:
Теперь Рику стало интересно, сколько елей существует в его матрице \(n \times m\). Помогите ему ответить на этот вопрос.
Выходные данные
Выведите единственное целое число — количество елок в матрице.
Примечание
В первом тестовом примере первая ель имеет вершину в точке \((1, 2)\) и высоту \(2\), вторая ель имеет вершину в точке \((1, 2)\) и высоту \(1\), третья ель имеет вершину в точке \((2, 1)\) и высоту \(1\), четвертая ель имеет вершину в точке \((2, 2)\) и высоту \(1\), пятая ель имеет вершину в точке \((2, 3)\) и высоту \(1\).
Во втором тестовом примере первая ель имеет вершину в точке \((1, 2)\) и высоту \(1\), вторая ель имеет вершину в точке \((2, 1)\) и высоту \(1\), третья ель имеет вершину в точке \((2, 2)\) и высоту \(1\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
2 3
.*.
***
2 3
.*.
**.
4 5
.***.
*****
*****
*.*.*
5 7
..*.*..
.*****.
*******
.*****.
..*.*..
|
5
3
23
34
|