# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

## Tour in Grid

You have a grid with n rows and m columns. Cell at the i^{th} row and the j^{th} column is called Cell(i, j) and id of the cell is G_{i,j}. Each cell has a unique id from 1 to n*m. You can jump from Cell(i,j) to Cell(x,y) by consuming power {(i-x)^{2}+(j-y)^{2}}*(G_{x,y}-G_{i,j}). In each day, you are going to select a number D. In that day, you can jump D cells, meaning if you are currently in a cell with id number p, then in one jump, you can go to another cell which id is (p+D). In the second jump you will be in (p+2*D), then (p+3*D) and so on. At k^{th} day, you have to go from p^{th} cell to q^{th} cell. You can select different D for each day. Now, you want to minimize the total power consumption.

### Input

Input starts with two integers n and m.

Each of the next n lines contain m integers representing the grid.

Then the next line contains one integer Q, representing the number of days.

The next Q lines will have the information of each day. In each line, there will be two id p and q.

**Constrains**

1 ≤ n, m ≤ 300

1 ≤ Q ≤ 10^{5}

1 ≤ p ≤ q ≤ n*m

### Output

For each day, you have to output minimum power on a line by itself.

### Samples

Input | Output |
---|---|

3 3 1 4 3 2 5 7 8 9 6 4 4 8 6 9 5 8 1 9 | 9 3 6 12 |

**Explanation:**

In the last day, you want to go from 1^{st} cell to 9^{th}. You can select 1,2,4,8 as the candidate values for D for that day. Otherwise you can not go from 1^{st} cell to 9^{th} cell.

^{2}+(1-1)

^{2}}*(2-1)+ {(2-1)

^{2}+(1-3)

^{2}}*(3-2)+ {(1-1)

^{2}+(3-2)

^{2}}*(4-3)+ {(1-2)

^{2}+(2-2)

^{2}}*(5-4)+ {(2-3)

^{2}+(2-3)

^{2}}*(6-5)+ {(3-2)

^{2}+(3-3)

^{2}}*(7-6)+ {(2-3)

^{2}+(3-1)

^{2}}*(8-7)+ {(3-3)

^{2}+(1-2)

^{2}}*(9-8) = 17

If you select 2 as D, you have to go through 1,3,5,7,9. The cost will be {(1-1)^{2}+(1-3)^{2}}*(3-1)+ {(1-2)^{2}+(3-2)^{2}}*(5-3)+ {(2-2)^{2}+(2-3)^{2}}*(7-5)+ {(2-3)^{2}+(3-2)^{2}}*(9-7)=18.

If you select 4 as D, you have to go through 1,5,9. The cost will be {(1-2)^{2}+(1-2)^{2}}*(5-1)+ {(2-3)^{2}+(2-2)^{2}}*(9-5) =12.

If you select 8 as D, you have to go through 1,9. The cost will be {(1-3)^{2}+(1-2)^{2}}*(9-1) =40

So, the minimum cost will be 12.