Igor is in the museum and he wants to see as many pictures as possible.

Museum can be represented as a rectangular field of n × m cells. Each cell is either empty or impassable. Empty cells are marked with '.', impassable cells are marked with '*'. Every two adjacent cells of different types (one empty and one impassable) are divided by a wall containing one picture.

At the beginning Igor is in some empty cell. At every moment he can move to any empty cell that share a side with the current one.

For several starting positions you should calculate the maximum number of pictures that Igor can see. Igor is able to see the picture only if he is in the cell adjacent to the wall with this picture. Igor have a lot of time, so he will examine every picture he can see.


-----Input-----

First line of the input contains three integers n, m and k (3 ≤ n, m ≤ 1000, 1 ≤ k ≤ min(n·m, 100 000)) — the museum dimensions and the number of starting positions to process.

Each of the next n lines contains m symbols '.', '*' — the description of the museum. It is guaranteed that all border cells are impassable, so Igor can't go out from the museum.

Each of the last k lines contains two integers x and y (1 ≤ x ≤ n, 1 ≤ y ≤ m) — the row and the column of one of Igor's starting positions respectively. Rows are numbered from top to bottom, columns — from left to right. It is guaranteed that all starting positions are empty cells.


-----Output-----

Print k integers — the maximum number of pictures, that Igor can see if he starts in corresponding position.


-----Examples-----
Input
5 6 3
******
*..*.*
******
*....*
******
2 2
2 5
4 3

Output
6
4
10

Input
4 4 1
****
*..*
*.**
****
3 2

Output
8

Difficulty: MEDIUM_HARD
Tags: Graph algorithms

Graph traversal

Shortest paths

Starter code:

Solutions:
import sys

def get_array():
	return list(map(int, sys.stdin.readline().split()))

def get_ints():
	return list(map(int, sys.stdin.readline().split()))

def input():
	return sys.stdin.readline().strip('\n')
cells = []

def dfs(x, y):
	nonlocal c
	q = [(x, y)]
	while q:
		(x, y) = q.pop()
		if x >= n or x < 0 or y >= m or (y < 0):
			continue
		if l[x][y] == '*':
			c += 1
			continue
		if visited[x][y]:
			continue
		visited[x][y] = 1
		cells.append((x, y))
		q.append((x + 1, y))
		q.append((x, y + 1))
		q.append((x - 1, y))
		q.append((x, y - 1))
(n, m, k) = get_ints()
l = []
for i in range(n):
	l.append(list(input()))
visited = []
out = []
for i in range(n + 10):
	visited.append([0] * (m + 10))
	out.append([-1] * (m + 10))
for i in range(n):
	for j in range(m):
		if not visited[i][j] and l[i][j] == '.':
			c = 0
			dfs(i, j)
			for x in cells:
				if visited[x[0]][x[1]] and out[x[0]][x[1]] == -1:
					out[x[0]][x[1]] = c
			cells.clear()
for i in range(k):
	(x, y) = get_ints()
	(x, y) = (x - 1, y - 1)
	print(out[x][y])


import sys

def get_array():
	return list(map(int, sys.stdin.readline().split()))

def get_ints():
	return map(int, sys.stdin.readline().split())

def input():
	return sys.stdin.readline().strip('\n')
(n, m, k) = get_ints()
visited = []
for i in range(n):
	visited.append([])
	for j in range(m):
		visited[i].append(0)
s = 0
d = {}

def dfs(x, y):
	global s
	s += 1
	c = 0
	q = [(x, y)]
	while q:
		(x, y) = q.pop()
		if x >= n or y >= m or x < 0 or (y < 0):
			return
		if l[x][y] == '*':
			c += 1
			continue
		if visited[x][y]:
			continue
		visited[x][y] = s
		q.append((x + 1, y))
		q.append((x - 1, y))
		q.append((x, y + 1))
		q.append((x, y - 1))
	d[s] = c
l = []
for i in range(n):
	l.append(input())
for i in range(n):
	for j in range(m):
		if not visited[i][j] and l[i][j] == '.':
			dfs(i, j)
for i in range(k):
	(x, y) = get_ints()
	x -= 1
	y -= 1
	print(d[visited[x][y]])


from sys import stdin
input = lambda : stdin.readline().strip()
from math import ceil, sqrt, factorial, gcd
from collections import deque
from bisect import bisect_left

def dfs(x, y):
	stack = [[x, y]]
	t = 0
	ne = {}
	while stack:
		(x, y) = stack.pop()
		if visited[x][y] == 0:
			visited[x][y] = 1
			if x in ne:
				ne[x].add(y)
			else:
				ne[x] = set()
				ne[x].add(y)
			for (a, b) in [[1, 0], [0, 1], [-1, 0], [0, -1]]:
				a = x + a
				b = y + b
				if l[a][b] == '*':
					t += 1
				elif visited[a][b] == 0:
					stack.append([a, b])
	for a in ne:
		for b in ne[a]:
			dp[a][b] = t
(n, m, k) = map(int, input().split())
l = [list(input()) for i in range(n)]
dp = [[0] * m for i in range(n)]
visited = [[0] * m for i in range(n)]
for i in range(n):
	for j in range(m):
		if l[i][j] == '.' and visited[i][j] == 0:
			dfs(i, j)
for i in range(k):
	(a, b) = map(int, input().split())
	print(dp[a - 1][b - 1])


import sys
input = sys.stdin.readline
(H, W, Q) = map(int, input().split())
S = [list(input())[:-1] for _ in range(H)]
vis = [0] * (H * W)
table = [0] * (H * W)
d = [-1, 0, 1, 0]
for i in range(H):
	for j in range(W):
		if vis[i * W + j]:
			continue
		if S[i][j] != '.':
			continue
		seen = 0
		s = [i * W + j]
		order = []
		while len(s):
			x = s.pop()
			order.append(x)
			if vis[x]:
				continue
			vis[x] = 1
			for k in range(4):
				u = x // W + d[k]
				v = x % W + d[-1 - k]
				if u in range(H) and v in range(W):
					if vis[u * W + v]:
						continue
					if S[u][v] == '.':
						s.append(u * W + v)
					elif S[u][v] == '*':
						seen += 1
		for x in order:
			table[x] = seen
for _ in range(Q):
	(y, x) = map(int, input().split())
	print(table[(y - 1) * W + x - 1])


import os
import sys
import math
from io import BytesIO, IOBase
from fractions import Fraction
import collections
from itertools import permutations
from collections import defaultdict
from collections import deque
import threading
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD

def dfs(start_n, start_m, cnt):
	ans = 0
	q = deque([(start_n, start_m)])
	visited[start_n][start_m] = cnt
	while q:
		(pos_n, pos_m) = q.pop()
		for (i, j) in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
			next_pos_n = pos_n + i
			next_pos_m = pos_m + j
			if 0 <= next_pos_n < n and 0 <= next_pos_m < m:
				if s[next_pos_n][next_pos_m] == '*':
					ans += 1
					continue
				if visited[next_pos_n][next_pos_m] == -1:
					visited[next_pos_n][next_pos_m] = cnt
					q.append((next_pos_n, next_pos_m))
	ans_memo[cnt] = ans
(n, m, k) = map(int, input().split())
s = [input() for i in range(n)]
info = [list(map(int, input().split())) for i in range(k)]
ans_memo = {}
next_pos = [0, 1]
visited = [[-1] * m for i in range(n)]
cnt = 0
for i in range(n):
	for j in range(m):
		if s[i][j] == '*' or visited[i][j] >= 0:
			continue
		dfs(i, j, cnt)
		cnt += 1
for i in range(k):
	(tmp_n, tmp_m) = info[i]
	tmp = visited[tmp_n - 1][tmp_m - 1]
	print(ans_memo[tmp])


import sys
(n, m, k) = map(int, input().split())
a = [sys.stdin.readline().rstrip() for _ in range(n)]
dp = [[0] * m for _ in range(n)]
for i in range(1, n - 1):
	for j in range(1, m - 1):
		if dp[i][j] != 0 or a[i][j] == '*':
			continue
		stack = [(i, j)]
		dp[i][j] = -1
		pic = 0
		while stack:
			(y, x) = stack.pop()
			for (ty, tx) in ((y + 1, x), (y - 1, x), (y, x + 1), (y, x - 1)):
				if dp[ty][tx] != 0:
					continue
				if a[ty][tx] == '*':
					pic += 1
				else:
					dp[ty][tx] = -1
					stack.append((ty, tx))
		dp[i][j] = pic
		stack.append((i, j))
		while stack:
			(y, x) = stack.pop()
			for (ty, tx) in ((y + 1, x), (y - 1, x), (y, x + 1), (y, x - 1)):
				if dp[ty][tx] != -1 or a[ty][tx] == '*':
					continue
				dp[ty][tx] = pic
				stack.append((ty, tx))
ans = [0] * k
for i in range(k):
	(x, y) = map(int, sys.stdin.readline().split())
	ans[i] = dp[x - 1][y - 1]
print(*ans, sep='\n')


import unittest
import sys
from collections import deque

def empty_around(i, rc, n, m, nw, mw):
	w = 32
	r = i // m // w
	c = i % m // w
	j = r * mw + c
	if j < len(rc):
		if rc[j] == 0:
			rc[j] = 1
			return (True, r, c)
	return (False, 0, 0)

def fill_around(a, r0, c0, to_visit, visited, n, m):
	w = 32
	for r in range(w):
		for c in range(w):
			i = (r0 * w + r) * m + (c0 * w + c)
			if r == 0 or r == w - 1 or c == 0 or (c == w - 1):
				if a[i] == 0:
					to_visit.append(i)
					a[i] = 1
			else:
				a[i] = 2
				visited.append(i)

class Igor:

	def __init__(self, test_inputs=None):
		it = iter(test_inputs.split('\n')) if test_inputs else None

		def uinput():
			return next(it) if it else sys.stdin.readline().rstrip()
		self.result = []
		w = 32
		(n, m, k) = [int(x) for x in uinput().split()]
		(d0, d1, d2, d3) = (-m, 2 * m, -m - 1, 2)
		a = []
		rc = []
		rr = []
		mw = m // w
		nw = n // w
		for _ in range(n):
			row = [0 if v == '.' else 3 for v in uinput()]
			a += row
			rc += [sum(row[i * w:i * w + w]) for i in range(mw)]
		for i in range(nw):
			j = i * mw * w
			rr += [sum([rc[j + u * mw + v] for u in range(w)]) for v in range(mw)]
		to_visit = deque()
		for _ in range(k):
			(x0, y0) = [int(x) - 1 for x in uinput().split()]
			i0 = x0 * m + y0
			step = 0
			if a[i0] > 3:
				self.result.append(a[i0])
			else:
				ans = 0
				to_visit.append(i0)
				visited = deque()
				step += 1
				while to_visit:
					i = to_visit.pop()
					if a[i] == 2:
						continue
					visited.append(i)
					if step % w == 1:
						(e, r0, c0) = empty_around(i, rr, n, m, nw, mw)
					else:
						e = False
					a[i] = 2
					if e:
						fill_around(a, r0, c0, to_visit, visited, n, m)
					for d in (d0, d1, d2, d3):
						i += d
						if a[i] == 0:
							to_visit.append(i)
							a[i] = 1
						elif a[i] == 3:
							ans += 1
				self.result.append(ans)
				for i in visited:
					a[i] = ans

	def calculate(self):
		return str('\n'.join(map(str, self.result)))

class unitTests(unittest.TestCase):

	def test_single_test(self):
		test = '5 6 3\n******\n*..*.*\n******\n*....*\n******\n2 2\n2 5\n4 3'
		d = Igor(test)
		self.assertEqual(Igor(test).calculate(), '6\n4\n10')
		test = ''
		test = ''
		test = ''

	def time_limit_test(self, nmax):
		import random
		import timeit
		test = str(nmax) + ' ' + str(nmax) + '\n'
		numnums = [str(i) + ' ' + str(i + 1) for i in range(nmax)]
		test += '\n'.join(numnums) + '\n'
		nums = [random.randint(1, 10000) for i in range(nmax)]
		test += ' '.join(map(str, nums)) + '\n'
		start = timeit.default_timer()
		d = Igor(test)
		calc = timeit.default_timer()
		d.calculate()
		stop = timeit.default_timer()
		print('\nTimelimit Test: ' + '{0:.3f}s (init {1:.3f}s calc {2:.3f}s)'.format(stop - start, calc - start, stop - calc))
sys.setrecursionlimit(100000)
if sys.argv[-1] == '-ut':
	unittest.main(argv=[' '])
sys.stdout.write(Igor().calculate())


import sys, io, os
from atexit import register
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
sys.stdout = io.BytesIO()
register(lambda : os.write(1, sys.stdout.getvalue()))
visited = [[0] * 1002 for _ in range(1002)]
out = [[-1] * 1002 for _ in range(1002)]
(n, m, k) = [int(x) for x in input().split()]
l = [input() for _ in range(n)]
Q = []
for j in range(m):
	for i in range(n):
		if not visited[i][j] and l[i][j] == b'.'[0]:
			c = 0
			Q.append((i, j))
			ind = 0
			while ind < len(Q):
				(x, y) = Q[ind]
				ind += 1
				if x >= n or x < 0 or y >= m or (y < 0):
					continue
				if l[x][y] == b'*'[0]:
					c += 1
					continue
				if visited[x][y]:
					continue
				visited[x][y] = 1
				Q.append((x + 1, y))
				Q.append((x, y + 1))
				Q.append((x - 1, y))
				Q.append((x, y - 1))
			while Q:
				(x, y) = Q.pop()
				out[x][y] = c
for i in range(k):
	(x, y) = [int(x) for x in input().split()]
	sys.stdout.write(str(out[x - 1][y - 1]).encode())
	sys.stdout.write(b'\n')


from collections import deque
from sys import stdin, stdout

def main():
	(n, m, k) = map(int, stdin.readline().split())
	mat = []
	for i in range(n):
		mat.append(stdin.readline())
	check = [[False for _ in range(m)] for _ in range(n)]
	queue = deque()
	dp = [[0 for _ in range(m)] for _ in range(n)]
	for i in range(n):
		for j in range(m):
			if mat[i][j] == '.' and (not check[i][j]):
				queue.append((i, j))
				check[i][j] = True
				comp = []
				count = 0
				while queue:
					(x, y) = queue.popleft()
					comp.append((x, y))
					dx = [0, 0, -1, 1]
					dy = [-1, 1, 0, 0]
					for tmp in range(4):
						if 0 <= x + dx[tmp] < n and 0 <= y + dy[tmp] < m and (not check[x + dx[tmp]][y + dy[tmp]]):
							if mat[x + dx[tmp]][y + dy[tmp]] == '*':
								count += 1
							elif mat[x + dx[tmp]][y + dy[tmp]] == '.':
								queue.append((x + dx[tmp], y + dy[tmp]))
								check[x + dx[tmp]][y + dy[tmp]] = True
				for (x, y) in comp:
					dp[x][y] = count
	for _ in range(k):
		(x, y) = map(int, stdin.readline().split())
		stdout.write(str(dp[x - 1][y - 1]))
		stdout.write('\n')
main()


import sys
input = sys.stdin.readline
from collections import *

class Unionfind:

	def __init__(self, n):
		self.par = [-1] * n
		self.rank = [1] * n

	def root(self, x):
		r = x
		while not self.par[r] < 0:
			r = self.par[r]
		t = x
		while t != r:
			tmp = t
			t = self.par[t]
			self.par[tmp] = r
		return r

	def unite(self, x, y):
		rx = self.root(x)
		ry = self.root(y)
		if rx == ry:
			return
		if self.rank[rx] <= self.rank[ry]:
			self.par[ry] += self.par[rx]
			self.par[rx] = ry
			if self.rank[rx] == self.rank[ry]:
				self.rank[ry] += 1
		else:
			self.par[rx] += self.par[ry]
			self.par[ry] = rx
(n, m, k) = map(int, input().split())
s = [input()[:-1] for _ in range(n)]
uf = Unionfind(n * m)
for i in range(n):
	for j in range(m):
		if s[i][j] == '.':
			if i + 1 < n and s[i + 1][j] == '.':
				uf.unite(m * i + j, m * (i + 1) + j)
			if j + 1 < m and s[i][j + 1] == '.':
				uf.unite(m * i + j, m * i + j + 1)
d = defaultdict(int)
for i in range(n):
	for j in range(m):
		if s[i][j] == '.':
			for (ni, nj) in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:
				if 0 <= ni < n and 0 <= nj < m and (s[ni][nj] == '*'):
					d[uf.root(m * i + j)] += 1
for _ in range(k):
	(x, y) = map(int, input().split())
	print(d[uf.root(m * (x - 1) + y - 1)])


import sys
input = lambda : sys.stdin.readline().rstrip()
from collections import deque
move = ([1, 0], [-1, 0], [0, 1], [0, -1])

def bfs(visited, sy, sx):
	if pic[sy][sx] != -1:
		return pic[sy][sx]
	queue = deque([[sy, sx]])
	visited.add(sy * m + sx)
	ans = 0
	while queue:
		(y, x) = queue.popleft()
		for (dy, dx) in move:
			(new_y, new_x) = (y + dy, x + dx)
			if museum[new_y][new_x] == '.':
				if new_y * m + new_x not in visited:
					visited.add(new_y * m + new_x)
					queue.append([new_y, new_x])
			else:
				ans += 1
	for a in visited:
		x = a % m
		y = a // m
		pic[y][x] = ans
	return ans
(n, m, k) = map(int, input().split())
museum = [input() for i in range(n)]
pic = [[-1 for i in range(m)] for j in range(n)]
for _ in range(k):
	(sy, sx) = map(int, input().split())
	(sy, sx) = (sy - 1, sx - 1)
	visited = set()
	print(bfs(visited, sy, sx))


import sys
(n, m, k) = map(int, input().split())
grid = []
for _ in range(n):
	grid.append(list(next(sys.stdin)))

def dfs(grid, xs, ys, g):
	stack = [(xs, ys)]
	grid[xs][ys] = g
	cnt = 0
	while len(stack):
		(i, j) = stack.pop()
		for (nx, ny) in ((i - 1, j), (i, j + 1), (i + 1, j), (i, j - 1)):
			if grid[nx][ny] == '*':
				cnt += 1
			elif grid[nx][ny] == '.':
				grid[nx][ny] = g
				stack.append((nx, ny))
	d[g] = cnt
d = [0] * k
g = 0
for _ in range(k):
	(i, j) = map(int, next(sys.stdin).split())
	if grid[i - 1][j - 1] == '.':
		dfs(grid, i - 1, j - 1, g)
	print(d[grid[i - 1][j - 1]])
	g += 1


from functools import cmp_to_key
from collections import deque, Counter
from heapq import heappush, heappop
from math import log, ceil
import sys
import os
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
if sys.version_info[0] < 3:
	(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
else:
	(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

def print(*args, **kwargs):
	(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(kwargs.pop('end', '\n'))
	if kwargs.pop('flush', False):
		file.flush()

def inp():
	return sys.stdin.readline().rstrip('\r\n')

def ii():
	return int(inp())

def si():
	return str(inp())

def li(lag=0):
	l = list(map(int, inp().split()))
	if lag != 0:
		for i in range(len(l)):
			l[i] += lag
	return l

def mi(lag=0):
	matrix = list()
	for i in range(n):
		matrix.append(li(lag))
	return matrix

def lsi():
	return list(map(str, inp().split()))

def print_list(lista, space=' ', **kwargs):
	print(space.join(map(str, lista)), **kwargs)

def bisect_left(a, x):
	left = 0
	right = len(a)
	while left < right:
		mid = (left + right) // 2
		if a[mid] < x:
			left = mid + 1
		else:
			right = mid
	return left

def bisect_right(a, x):
	left = 0
	right = len(a)
	while left < right:
		mid = (left + right) // 2
		if a[mid] > x:
			right = mid
		else:
			left = mid + 1
	return left

def bisect_elements(a, x):
	return bisect_right(a, x) - bisect_left(a, x)
MOD = 10 ** 9 + 7
maxN = 5
FACT = [0] * maxN
INV_FACT = [0] * maxN

def add(x, y):
	return (x + y) % MOD

def multiply(x, y):
	return x * y % MOD

def power(x, y):
	if y == 0:
		return 1
	elif y % 2:
		return multiply(x, power(x, y - 1))
	else:
		a = power(x, y // 2)
		return multiply(a, a)

def inverse(x):
	return power(x, MOD - 2)

def divide(x, y):
	return multiply(x, inverse(y))

def allFactorials():
	FACT[0] = 1
	for i in range(1, maxN):
		FACT[i] = multiply(i, FACT[i - 1])

def inverseFactorials():
	n = len(INV_FACT)
	INV_FACT[n - 1] = inverse(FACT[n - 1])
	for i in range(n - 2, -1, -1):
		INV_FACT[i] = multiply(INV_FACT[i + 1], i + 1)

def coeffBinom(n, k):
	if n < k:
		return 0
	return multiply(FACT[n], multiply(INV_FACT[k], INV_FACT[n - k]))

def create_graph(n, m, undirected=1, unweighted=1):
	graph = [[] for i in range(n)]
	if unweighted:
		for i in range(m):
			[x, y] = li(lag=-1)
			graph[x].append(y)
			if undirected:
				graph[y].append(x)
	else:
		for i in range(m):
			[x, y, w] = li(lag=-1)
			w += 1
			graph[x].append([y, w])
			if undirected:
				graph[y].append([x, w])
	return graph

def create_tree(n, unweighted=1):
	children = [[] for i in range(n)]
	if unweighted:
		for i in range(n - 1):
			[x, y] = li(lag=-1)
			children[x].append(y)
			children[y].append(x)
	else:
		for i in range(n - 1):
			[x, y, w] = li(lag=-1)
			w += 1
			children[x].append([y, w])
			children[y].append([x, w])
	return children

def dist(tree, n, A, B=-1):
	s = [[A, 0]]
	(massimo, massimo_nodo) = (0, 0)
	distanza = -1
	v = [-1] * n
	while s:
		(el, dis) = s.pop()
		if dis > massimo:
			massimo = dis
			massimo_nodo = el
		if el == B:
			distanza = dis
		for child in tree[el]:
			if v[child] == -1:
				v[child] = 1
				s.append([child, dis + 1])
	return (massimo, massimo_nodo, distanza)

def diameter(tree):
	(_, foglia, _) = dist(tree, n, 0)
	(diam, _, _) = dist(tree, n, foglia)
	return diam

def dfs(graph, n, A):
	v = [-1] * n
	s = [[A, 0]]
	v[A] = 0
	while s:
		(el, dis) = s.pop()
		for child in graph[el]:
			if v[child] == -1:
				v[child] = dis + 1
				s.append([child, dis + 1])
	return v

def bfs(graph, n, A):
	v = [-1] * n
	s = deque()
	s.append([A, 0])
	v[A] = 0
	while s:
		(el, dis) = s.popleft()
		for child in graph[el]:
			if v[child] == -1:
				v[child] = dis + 1
				s.append([child, dis + 1])
	return v

def parents_children_root_unrooted_tree(tree, n, root=0):
	q = deque()
	visited = [0] * n
	parent = [-1] * n
	children = [[] for i in range(n)]
	q.append(root)
	while q:
		all_done = 1
		visited[q[0]] = 1
		for child in tree[q[0]]:
			if not visited[child]:
				all_done = 0
				q.appendleft(child)
		if all_done:
			for child in tree[q[0]]:
				if parent[child] == -1:
					parent[q[0]] = child
					children[child].append(q[0])
			q.popleft()
	return (parent, children)

def all_longest_path_passing_from_node(parent, children, n):
	q = deque()
	visited = [len(children[i]) for i in range(n)]
	downwards = [[0, 0] for i in range(n)]
	upward = [1] * n
	longest_path = [1] * n
	for i in range(n):
		if not visited[i]:
			q.append(i)
			downwards[i] = [1, 0]
	while q:
		node = q.popleft()
		if parent[node] != -1:
			visited[parent[node]] -= 1
			if not visited[parent[node]]:
				q.append(parent[node])
		else:
			root = node
		for child in children[node]:
			downwards[node] = sorted([downwards[node][0], downwards[node][1], downwards[child][0] + 1], reverse=True)[0:2]
	s = [node]
	while s:
		node = s.pop()
		if parent[node] != -1:
			if downwards[parent[node]][0] == downwards[node][0] + 1:
				upward[node] = 1 + max(upward[parent[node]], downwards[parent[node]][1])
			else:
				upward[node] = 1 + max(upward[parent[node]], downwards[parent[node]][0])
		longest_path[node] = downwards[node][0] + downwards[node][1] + upward[node] - min([downwards[node][0], downwards[node][1], upward[node]]) - 1
		for child in children[node]:
			s.append(child)
	return longest_path

def ok(x, y, t):
	n = len(t)
	m = len(t[0])
	return x > -1 and y > -1 and (x < n) and (y < m)

def visita(x, y, t):
	if pic[x][y] != -1:
		return pic[x][y]
	stack = list()
	stack.append([x, y])
	visti = set()
	visti.add(x * m + y)
	d = [-1, 0, 1, 0, -1]
	count = 0
	while stack:
		(x, y) = stack.pop()
		for i in range(4):
			X = x + d[i]
			Y = y + d[i + 1]
			if ok(X, Y, t):
				if t[X][Y] == '*':
					count += 1
				elif X * m + Y not in visti:
					visti.add(X * m + Y)
					stack.append([X, Y])
	for a in visti:
		y = a % m
		x = a // m
		pic[x][y] = count
	return count
(n, m, k) = li()
t = list()
for i in range(n):
	s = si()
	t.append(s)
pic = [[-1 for i in range(m)] for j in range(n)]
for i in range(k):
	(x, y) = li()
	x -= 1
	y -= 1
	print(visita(x, y, t))


import os, sys
from io import BytesIO, IOBase
from collections import deque

def main():
	(n, m, Q) = map(int, input().split())
	arr = [input().strip() for _ in range(n)]
	dp = [[0] * m for _ in range(n)]
	(ans, comp, dx, dy) = ([], 0, [-1, 1, 0, 0], [0, 0, -1, 1])
	for i in range(n):
		for j in range(m):
			if dp[i][j] or arr[i][j] == '*':
				continue
			comp += 1
			val = 0
			dp[i][j] = comp
			curr = deque([(i, j)])
			while len(curr):
				(x, y) = curr.popleft()
				for k in range(4):
					(x1, y1) = (x + dx[k], y + dy[k])
					if arr[x1][y1] != '*' and (not dp[x1][y1]):
						curr.append((x1, y1))
						dp[x1][y1] = comp
					elif arr[x1][y1] == '*':
						val += 1
			ans.append(val)
	for _ in range(Q):
		(a, b) = map(lambda xx: int(xx) - 1, input().split())
		if not dp[a][b]:
			print(0)
		else:
			print(ans[dp[a][b] - 1])
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import sys
input = lambda : sys.stdin.readline().rstrip()
from collections import deque
(N, M, K) = map(int, input().split())
room = [input() for i in range(N)]
memo = [[-1 for __ in range(M)] for _ in range(N)]
for i in range(K):
	(a, b) = map(int, input().split())
	if memo[a - 1][b - 1] != -1:
		print(memo[a - 1][b - 1])
		continue
	deq = deque([(a - 1, b - 1)])
	ans = 0
	trace = {(a - 1) * M + (b - 1)}
	while len(deq) != 0:
		(x, y) = deq.popleft()
		for (p, q) in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:
			if room[p][q] == '*':
				ans += 1
			elif p * M + q not in trace:
				deq.append((p, q))
				trace.add(p * M + q)
	for a in trace:
		tx = a // M
		ty = a % M
		memo[tx][ty] = ans
	print(ans)


import sys, io, os
from atexit import register
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
sys.stdout = io.BytesIO()
register(lambda : os.write(1, sys.stdout.getvalue()))

def print(args=[], sep=' ', end='\n', file=sys.stdout):
	first = True
	sep = sep.encode()
	for a in args:
		if first:
			first = False
		else:
			file.write(sep)
		file.write(str(a).encode())
	file.write(end.encode())
visited = [[0] * 1010 for _ in range(1010)]
out = [[-1] * 1010 for _ in range(1010)]
cells = []

def dfs(x, y):
	global c
	Q = [(x, y)]
	while Q:
		(x, y) = Q.pop()
		if x >= n or x < 0 or y >= m or (y < 0):
			continue
		if l[x][y] == b'*'[0]:
			c += 1
			continue
		if visited[x][y]:
			continue
		visited[x][y] = 1
		cells.append((x, y))
		Q.append((x + 1, y))
		Q.append((x, y + 1))
		Q.append((x - 1, y))
		Q.append((x, y - 1))
(n, m, k) = [int(x) for x in input().split()]
l = [input() for _ in range(n)]
for i in range(n):
	for j in range(m):
		if not visited[i][j] and l[i][j] == b'.'[0]:
			c = 0
			dfs(i, j)
			while cells:
				x = cells.pop()
				if visited[x[0]][x[1]] and out[x[0]][x[1]] == -1:
					out[x[0]][x[1]] = c
ANS = []
for i in range(k):
	(x, y) = [int(x) for x in input().split()]
	ANS.append(out[x - 1][y - 1])
print(ANS, sep='\n')


import sys
from queue import deque
move = [(0, 1), (1, 0), (0, -1), (-1, 0)]
(n, m, k) = map(int, sys.stdin.readline().split())
a = []
for i in range(n):
	a.append(sys.stdin.readline().rstrip())
visited = []
values = []
for x in range(n):
	visited.append([])
	values.append([])
	for y in range(m):
		visited[x].append(False)
		values[x].append(0)
for x in range(n):
	for y in range(m):
		if a[x][y] == '*' or visited[x][y]:
			continue
		q = deque()
		visited[x][y] = True
		q.append((x, y))
		sum = 0
		connected = [(x, y)]
		while len(q) != 0:
			cur = q.pop()
			for l in move:
				tx = cur[0] + l[0]
				ty = cur[1] + l[1]
				if tx < 0 or tx >= n or ty < 0 or (ty >= m):
					continue
				if a[tx][ty] == '.' and visited[tx][ty]:
					continue
				if a[tx][ty] == '*':
					sum += 1
					continue
				q.append((tx, ty))
				visited[tx][ty] = True
				connected.append((tx, ty))
		for c in connected:
			values[c[0]][c[1]] = sum
for i in range(k):
	(x, y) = map(int, sys.stdin.readline().split())
	print(values[x - 1][y - 1])


import sys
(M, N, K) = map(int, input().split())
A = []
for _ in range(M):
	A.append(list(next(sys.stdin)))
cnt = {}
gid = 0
for i in range(M):
	for j in range(N):
		if A[i][j] != '.':
			continue
		gid += 1
		A[i][j] = gid
		k = 0
		stk = [(i, j)]
		while stk:
			(ii, jj) = stk.pop()
			if A[ii][jj] != gid:
				continue
			for (ni, nj) in ((ii - 1, jj), (ii, jj + 1), (ii + 1, jj), (ii, jj - 1)):
				if A[ni][nj] == '*':
					k += 1
				elif A[ni][nj] == '.':
					A[ni][nj] = gid
					stk.append((ni, nj))
		cnt[gid] = k
for _ in range(K):
	ln = next(sys.stdin)
	(i, j) = map(int, ln.split())
	(i, j) = (i - 1, j - 1)
	print(cnt[A[i][j]])


import sys
import heapq
import math
sys.setrecursionlimit(100000)
input = sys.stdin.readline
print = sys.stdout.write
from collections import deque
from collections import defaultdict
from collections import Counter
modH = int(10 ** 9) + 7
I = lambda : list(map(int, input().split(' ')))

def PRINT(lst, sep=' '):
	print(sep.join(map(str, lst)))
(n, m, k) = I()
graph = [input() for i in range(n)]
queries = [I() for j in range(k)]
nums = [[0 for j in range(m)] for i in range(n)]

def get(x, y):
	global nums
	ret = []
	cnt = 0
	for (a, b) in [(x, y + 1), (x + 1, y), (x - 1, y), (x, y - 1)]:
		if a >= 0 and b >= 0 and (a < n) and (b < m) and (graph[a][b] == '.'):
			cnt += 1
			ret.append((a, b))
	nums[x][y] = 4 - cnt
	return ret
visited = [[0 for j in range(m)] for i in range(n)]
ans = {}

def bfs(aa, cmp):
	(x, y) = aa
	queue = deque()
	queue.append((x, y))
	visited[x][y] = cmp
	get(x, y)
	cnt = 0
	while queue:
		cur = queue.popleft()
		get(cur[0], cur[1])
		cnt += nums[cur[0]][cur[1]]
		for (a, b) in get(cur[0], cur[1]):
			if not visited[a][b]:
				queue.append((a, b))
				visited[a][b] = cmp
	ans[cmp] = cnt
fin_ans = []
cmp = 1
for i in range(n):
	for j in range(m):
		if not visited[i][j] and graph[i][j] == '.':
			bfs((i, j), cmp)
			cmp += 1
for (x, y) in queries:
	fin_ans.append(ans[visited[x - 1][y - 1]])
PRINT(fin_ans, sep='\n')


import sys
Ri = lambda : [int(x) for x in sys.stdin.readline().split()]
ri = lambda : sys.stdin.readline().strip()

def input():
	return sys.stdin.readline().strip()

def list2d(a, b, c):
	return [[c] * b for i in range(a)]

def list3d(a, b, c, d):
	return [[[d] * c for j in range(b)] for i in range(a)]

def list4d(a, b, c, d, e):
	return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]

def ceil(x, y=1):
	return int(-(-x // y))

def INT():
	return int(input())

def MAP():
	return map(int, input().split())

def LIST(N=None):
	return list(MAP()) if N is None else [INT() for i in range(N)]

def Yes():
	print('Yes')

def No():
	print('No')

def YES():
	print('YES')

def NO():
	print('NO')
INF = 10 ** 18
MOD = 998244353
N = 10 ** 7 + 1

def ok(i, j):
	if 0 <= i < n and 0 <= j < m:
		return True
	return False

def dfs(i, j):
	ans = 0
	sta = [(i, j)]
	while sta:
		(i, j) = sta.pop()
		if not vis[i][j]:
			vis[i][j] = True
			if ok(i + 1, j):
				if st[i + 1][j] == '*':
					ans += 1
				elif not vis[i + 1][j]:
					dic[i + 1][j] = ite
					sta.append((i + 1, j))
			if ok(i - 1, j):
				if st[i - 1][j] == '*':
					ans += 1
				elif not vis[i - 1][j]:
					dic[i - 1][j] = ite
					sta.append((i - 1, j))
			if ok(i, j + 1):
				if st[i][j + 1] == '*':
					ans += 1
				elif not vis[i][j + 1]:
					dic[i][j + 1] = ite
					sta.append((i, j + 1))
			if ok(i, j - 1):
				if st[i][j - 1] == '*':
					ans += 1
				elif not vis[i][j - 1]:
					dic[i][j - 1] = ite
					sta.append((i, j - 1))
	return ans
(n, m, k) = Ri()
st = []
for i in range(n):
	temp = ri()
	st.append(temp)
vis = list2d(n, m, False)
dp = list2d(n, m, 0)
ite = -1
dic = list2d(n, m, -1)
dicans = [0] * 10 ** 6
for i in range(n):
	for j in range(m):
		if st[i][j] != '*' and vis[i][j] == False:
			ite += 1
			dic[i][j] = ite
			tans = dfs(i, j)
			dicans[ite] = tans
if n != 1000:
	for _ in range(k):
		(r, c) = Ri()
		r -= 1
		c -= 1
		tite = dic[r][c]
		print(dicans[tite])
else:
	for _ in range(k):
		(r, c) = Ri()
		r -= 1
		c -= 1
		tite = dic[r][c]
		print(dicans[tite])


import sys
input = sys.stdin.readline
(H, W, N) = map(int, input().split())
G = [input().rstrip() for _ in range(H)]
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
visited = [[0 for j in range(W)] for i in range(H)]
picture = [[0 for j in range(W)] for i in range(H)]
for i in range(H):
	for j in range(W):
		if G[i][j] == '*' or visited[i][j]:
			continue
		stack = [(i, j)]
		memo = [(i, j)]
		visited[i][j] = 1
		p = 0
		while stack:
			(x, y) = stack.pop()
			for k in range(4):
				(nx, ny) = (x + dx[k], y + dy[k])
				if not (0 <= nx < H and 0 <= ny < W) or visited[nx][ny]:
					continue
				if G[nx][ny] == '*':
					p += 1
					continue
				visited[nx][ny] = 1
				stack.append((nx, ny))
				memo.append((nx, ny))
		for (x, y) in memo:
			picture[x][y] = p
res = []
for _ in range(N):
	(x, y) = map(lambda a: int(a) - 1, input().split())
	res.append(picture[x][y])
print('\n'.join(map(str, res)))


import sys
(M, N, K) = map(int, input().split())
A = []
for _ in range(M):
	A.append(list(next(sys.stdin)))
d = {}

def dfs(i, j, g):
	A[i][j] = g
	stk = [(i, j)]
	cnt = 0
	while stk:
		(i, j) = stk.pop()
		for (ni, nj) in ((i - 1, j), (i, j + 1), (i + 1, j), (i, j - 1)):
			if A[ni][nj] == '*':
				cnt += 1
			elif A[ni][nj] == '.':
				A[ni][nj] = g
				stk.append((ni, nj))
	d[g] = cnt
g = 0
for _ in range(K):
	ln = next(sys.stdin)
	(i, j) = map(int, ln.split())
	(i, j) = (i - 1, j - 1)
	if A[i][j] == '.':
		g += 1
		dfs(i, j, g)
	print(d[A[i][j]])


import collections
import sys
input = sys.stdin.readline
(n, m, k) = map(int, input().split())
mu = [input() for _ in range(n)]
colored = [[0] * m for _ in range(n)]

def paint_and_count(x, y, col):
	s = 0
	q = collections.deque()
	if mu[x][y] == '*':
		return 0
	colored[x][y] = col
	q.append((x, y))
	while q:
		(x, y) = q.popleft()
		x = x + 1
		if mu[x][y] == '.' and colored[x][y] == 0:
			colored[x][y] = col
			q.append((x, y))
		elif mu[x][y] == '*':
			s += 1
		x = x - 2
		if mu[x][y] == '.' and colored[x][y] == 0:
			colored[x][y] = col
			q.append((x, y))
		elif mu[x][y] == '*':
			s += 1
		(x, y) = (x + 1, y + 1)
		if mu[x][y] == '.' and colored[x][y] == 0:
			colored[x][y] = col
			q.append((x, y))
		elif mu[x][y] == '*':
			s += 1
		y = y - 2
		if mu[x][y] == '.' and colored[x][y] == 0:
			colored[x][y] = col
			q.append((x, y))
		elif mu[x][y] == '*':
			s += 1
	return s
d = [0]
queries = [list(map(int, input().split())) for i in range(k)]
color = 1
for (x, y) in queries:
	if mu[x - 1][y - 1] == '.':
		if not colored[x - 1][y - 1]:
			d.append(paint_and_count(x - 1, y - 1, color))
			color += 1
		print(d[colored[x - 1][y - 1]])
	else:
		print(0)


from collections import deque
import sys
input = sys.stdin.readline

def dfs(start_n, start_m, cnt):
	ans = 0
	q = deque([(start_n, start_m)])
	visited[start_n][start_m] = cnt
	while q:
		(pos_n, pos_m) = q.pop()
		for (i, j) in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
			next_pos_n = pos_n + i
			next_pos_m = pos_m + j
			if 0 <= next_pos_n < n and 0 <= next_pos_m < m:
				if s[next_pos_n][next_pos_m] == '*':
					ans += 1
					continue
				if visited[next_pos_n][next_pos_m] == -1:
					visited[next_pos_n][next_pos_m] = cnt
					q.append((next_pos_n, next_pos_m))
	ans_memo[cnt] = ans
(n, m, k) = map(int, input().split())
s = [input() for i in range(n)]
info = [list(map(int, input().split())) for i in range(k)]
ans_memo = {}
next_pos = [0, 1]
visited = [[-1] * m for i in range(n)]
cnt = 0
for i in range(n):
	for j in range(m):
		if s[i][j] == '*' or visited[i][j] >= 0:
			continue
		dfs(i, j, cnt)
		cnt += 1
for i in range(k):
	(tmp_n, tmp_m) = info[i]
	tmp = visited[tmp_n - 1][tmp_m - 1]
	print(ans_memo[tmp])