The building of Middle Earth Technical University Faculty of Engineering needs to be painted urgently. For this purpose, the dean asked you to find the number of walls each painter can paint.

You are given the building plan and the locations of the painters. The building has rooms and walls, and painters are located in arbitrary rooms in this building. The walls are marked with "*" and empty cells are marked with ".". Painters are always located on empty cells (".") and all cells on the building's borders are walls ("*").

A painter can freely walk in the room they're in, but cannot go past walls or move to other rooms. So they can only paint the room they are in. The number of cells they are able to paint is the number of walls ("*") the room borders.

Two or more painters can be \(\underline{\text{in same room}}\) and different painters can paint the same walls again since each of them has different colors. Can you find the number of walls that each painter will be able to paint?

Input

First line consists of 3 integers: \(\mathbf{N}\) (row count), \(\mathbf{M}\) (column count), and \(\mathbf{K}\) (number of painters). Rows are numbered from \(1\) to \(\mathbf{N}\) and columns from \(1\) to \(\mathbf{M}\).

Then, following \(\mathbf{N}\) line, you will be given an \(\mathbf{NxM}\) grid consisting of "." and "*". "." will represent rooms, and "*" will represent walls.

Then, following \(\mathbf{K}\) lines, you will be given two integers \(\mathbf{X}\) and \(\mathbf{Y}\), the locations of painters. \(\mathbf{X}\) denotes their row number (top to bottom) and \(\mathbf{Y}\) denotes their column number (left to right).

• \(1 \leq \mathbf{N}, \mathbf{M} \leq 1000\)
• \(1 \leq \mathbf{K} \leq \mathbf{N \cdot M}\)
• \(1 \leq \mathbf{X} \leq \mathbf{N}\)
• \(1 \leq \mathbf{Y} \leq \mathbf{M}\)

Output

In \(\mathbf{K}\) lines, you should print the number of walls' sides that the painters can paint.

Examples:

Input:

6 6 3
******
*.*..*
*.**.*
******
*....*
******
2 2
3 5
5 5

Output:

6
8
10

Input:

7 6 3
******
*....*
*.****
***..*
*....*
*....*
******
2 2
6 5
4 5

Output:

12
14
14

Explanation

Input-2

First painter is located (2,2). The painter is able to paint one of each wall except the wall located (3,3) of which the painter can paint two sides. In total, the painter can paint 12.

The second painter is located (6,5). The painter is able to paint one of each wall except the wall located (4,3) of which the painter can paint two sides. In total, the painter can paint 14.

The second painter is located (4,5) and in the same room as the previous painter. However, the painter is able to paint this room again. In total, the painter can paint 14.