Consider a block of m rows and n columns. At each step you can move one step to the right or one step to bottom or one step to bottom-right.

i.e.   if you are currently at (x, y)      : x-row, y-column

You can either move to (x, y+1) or (x+1, y) or (x+1, y+1)

You’ve to find the number of possibilities to reach the point (A, B) from (0, 0).

Unluckily you cannot step into some places where bombs are placed denoted by “@”.

Input

The first line consists of 2 integers m and n denotes the number of rows and columns.

Then the description of the m × n block is given.

(‘0’- if the path is free to move and ‘@’-if the path has bombs and you cannot move to that place.)

Then an integer t follows which denotes the number of test cases.

Then for next t lines each line consists of 2 integers A and B.

Output

For each test case print the number of ways to reaching (A, B) from (0, 0) in separate lines.

Constraints

2 ≤ m ≤ 10

2 ≤ n ≤ 10

0 ≤ A < m

0 ≤ B < n

Example:

Input
3 6
000@@@
@@00@@
@@000@
8
0 1
0 4
1 3
2 3
2 4
1 2
2 2
2 5

Output
1
0
3
7
10
2
2
0