D. Игорь в музее
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Игорь пришёл в музей и хочет посмотреть на как можно большее количество картин.

Музей представляет собой прямоугольное клетчатое поле размером n × m. Каждая клетка либо является пустой и обозначена символом '.', либо является непроходимой и обозначена символом '*'. Любую пару соседних по стороне клеток, одна из которых пустая, а другая непроходимая, разделяет стена, на которой висит картина.

Игорь всегда начинает в некоторой пустой клетке. В любой момент времени Игорь может переместиться в любую из четырёх соседних по стороне клеток, если она является пустой.

Ваша задача для нескольких начальных положений Игоря определить максимальное количество картин, которые он сможет посмотреть. Игорь может посмотреть на картину, если находится в клетке, одной из сторон которой является стена с данной картиной. Можно считать, что Игорю всегда хватит времени, чтобы сколь угодно долго перемещаться по музею и смотреть на картины.

Входные данные

В первой строке входных данных записаны три числа n, m и k (3 ≤ n, m ≤ 1000, 1 ≤ k ≤ min(n·m, 100 000)) — размеры музея и количество начальных положений, для которых нужно определить требуемую величину.

В следующих n строках находится по m символов '.', '*', описывающих музей. Гарантируется, что все граничные клетки непроходимы, то есть Игорь никогда не сможет выйти из музей.

Далее в k строках находится по два целых положительных числа x и y (1 ≤ x ≤ n, 1 ≤ y ≤ m) — номер строки и номер столбца для одного из начальных положений Игоря. Строки нумеруются с единицы сверху вниз, а столбцы — слева направо. Гарантируется, что все начальные положения находятся в пустых клетках.

Выходные данные

Выведите k целых чисел — максимальное количество картин, которые сможет посмотреть Игорь, для каждого начального положения.

Примеры
Входные данные
5 6 3
******
*..*.*
******
*....*
******
2 2
2 5
4 3
Выходные данные
6
4
10
Входные данные
4 4 1
****
*..*
*.**
****
3 2
Выходные данные
8