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