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 Gi,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(Gx,y−Gi,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+2D), then (p+3D) 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 (1≤n,m≤300).
Each of the next n lines contain m integers representing the grid. Then the next line contains one integer Q (1≤Q≤105), 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 (1≤p≤q≤n×m).
Output
For each day, you have to output minimum power on a line by itself.
Sample
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
In the last day, you want to go from 1st cell to 9th. You can select 1, 2, 4, 8 as the candidate values for D for that day. Otherwise you can not go from 1st cell to 9th cell.
If you select 1 as D, you have to go through 1, 2, 3, 4, 5, 6, 7, 8, 9. The cost will be (1−2)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
