using System;
using System.Collections.Generic;

namespace Guzva
{
    class Program
    {
        static void Main(string[] args)
        {
            int n, m;
            string red;
            red = Console.ReadLine();
            n = int.Parse(red.Split(' ')[0].ToString());
            m = int.Parse(red.Split(' ')[1].ToString());
            int[,] matrix = new int[n, m];
            int[,] duzine = new int[n, m];
            for (int i = 0; i < n; i++)
            {
                red = Console.ReadLine();
                string[] pom = red.Split(' ');
                for (int j = 0; j < m; j++)
                {
                    matrix[i, j] = int.Parse(pom[j]);
                    duzine[i, j] = int.MaxValue;
                }
            }
            int Q = int.Parse(Console.ReadLine());
            int[,] zatvorenaPolja = new int[Q, 2];
            for (int i = 0; i < Q; i++)
            {
                red = Console.ReadLine();
                zatvorenaPolja[i, 0] = int.Parse(red.Split(' ')[0]);
                zatvorenaPolja[i, 1] = int.Parse(red.Split(' ')[1]);
            }
            for (int i = 0; i < Q; i++)
            {
                Dijkstra(matrix, duzine, zatvorenaPolja[i,0]-1, zatvorenaPolja[i,1]-1);
                Console.WriteLine(duzine[n - 1, m - 1]);
            }
        }
        static void Dijkstra(int[,] matrix, int[,] distance, int zx, int zy)
        {
            int n = matrix.GetLength(0);
            int m = matrix.GetLength(1);

            distance[0, 0] = matrix[0, 0];
            var pq = new SortedList<int, Tuple<int, int>>();
            pq.Add(0, new Tuple<int, int>(0, 0));

            while (pq.Count > 0)
            {
                var top = pq.Keys[0];
                int x1 = pq.Values[0].Item1;
                int y1 = pq.Values[0].Item2;
                
                pq.RemoveAt(0);
                if (x1 == zx && y1 == zy) continue;
                for (int i = 0; i <= 1; i++)
                {
                    for (int j = 0; j <= 1; j++)
                    {
                        if (Math.Abs(i) == Math.Abs(j)) continue;
                        int nx = x1 + i;
                        int ny = y1 + j;
                        if (nx == zx && ny == zy) continue;
                        if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
                        if (distance[nx, ny] > distance[x1, y1] + matrix[nx, ny])
                        {
                            distance[nx, ny] = distance[x1, y1] + matrix[nx, ny];
                            pq.Add(-distance[nx, ny], new Tuple<int, int>(nx, ny));
                        }
                    }
                }
            }
        }
    }
}