Игорь пришёл в музей и хочет посмотреть на как можно большее количество картин.
Музей представляет собой прямоугольное клетчатое поле размером n × m. Каждая клетка либо является пустой и обозначена символом '.', либо является непроходимой и обозначена символом '*'. Любую пару соседних по стороне клеток, одна из которых пустая, а другая непроходимая, разделяет стена, на которой висит картина.
Игорь всегда начинает в некоторой пустой клетке. В любой момент времени Игорь может переместиться в любую из четырёх соседних по стороне клеток, если она является пустой.
Ваша задача для нескольких начальных положений Игоря определить максимальное количество картин, которые он сможет посмотреть. Игорь может посмотреть на картину, если находится в клетке, одной из сторон которой является стена с данной картиной. Можно считать, что Игорю всегда хватит времени, чтобы сколь угодно долго перемещаться по музею и смотреть на картины.
Выходные данные
Выведите k целых чисел — максимальное количество картин, которые сможет посмотреть Игорь, для каждого начального положения.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 6 3
******
*..*.*
******
*....*
******
2 2
2 5
4 3
|
6
4
10
|
|
2
|
4 4 1
****
*..*
*.**
****
3 2
|
8
|