Problem A
Nordic Camping

When camping in the highlands of the Nordic countries, having a reliable source of water can be a matter of life and death. Traditionally Nordic campers have always pitched their tents over a water source such that water can be fetched at any time without having to go outside. Another bizarre tradition of the Nordic people is their tents. They only use square tents.

The campsites in the Nordic highlands can be very rough and rocky. Jon is currently setting up a new campsite and has surveyed all the usable spots on the campsite. Modeling the campsite as an $N$ by $M$ grid, Jon gives you a list of all the cells that are rough, and thus unusable. Jon now wants to figure out what is the largest tent that can be pitched on his campsite, only making use of smooth, usable cells, so that it covers a given water source.

For each water source, can you help Jon determine the size of the largest square tent that can be pitched so that it covers that particular water source?

Figure 1: The second example test case and the area of the largest square tent that covers the water source at $(3,2)$. This also happens to be the largest square tent that covers the water source at $(5,4)$.

Input

The first line of input contains two integers, $N$ and $M$ ($1\leq N,M$). Then follow $N$ lines with $M$ characters on each line, describing the map for the possible campsites. Each character in the map is either . (indicating a usable cell) or # (indicating an unusable cell).

Then follows a line with a single integer $Q$, the number of water sources Jon has under consideration. Each of the following $Q$ lines contains two integers $r$ and $c$ ($1\leq r\leq N$, $1\leq c\leq M$), giving the location $(r,c)$ of a water source.

Output

For each water source Jon has under consideration, in the same order as in the input, output the ground area of the largest square tent that can be pitched on smooth, usable cells so that it covers that particular water source.

Note that the tent may not be pitched so that it partially covers a cell. Either it covers it completely, or has an empty intersection with the cell.

Grading

Your solution will be graded on a set of subtasks. A subtask will consist of multiple test cases. To get the points for a subtask, your solution must pass all test cases that are part of the subtask.

3 3
#..
...
.##
2
1 3
2 1

4
1

5 5
#...#
..#..
.....
#...#
#....
5
3 2
2 5
5 4
4 5
1 3

9
4
9
0
1