TIOJ 1034

#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <utility>
#ifdef TEST
    #define debug(...) printf(__VA_ARGS__)
#else
    #define debug(...) (void)0
#endif
#define EB emplace_back
#define MP make_pair
#define ST first
#define ND second
using namespace std;
using ll = long long;
using llu = long long unsigned;
using pii = pair<int,int>;
/************************/
#define INF 100000000
#define MXN 20
int N;
int grid[MXN+5][MXN+5]; // y , x
pii path[MXN+5][MXN+5][MXN+5][MXN+5]; // y1, x1, y2, x2 => ST: best path, ND: Bomb best path
void FloydWarshall();
void Init();
int main(){
    int Q;
    scanf("%d", &N);
    for(int i = 0 ; i < N; ++i)
        for(int j = 0 ; j < N ; ++j)
            scanf("%d", &grid[j][i]);
    Init();
    FloydWarshall();
    scanf("%d", &Q);
    while(Q--){
        pii p1, p2;
        scanf("%d%d%d%d", &p1.ST, &p1.ND, &p2.ST, &p2.ND);
        pii ans = path[p1.ND-1][p1.ST-1][p2.ND-1][p2.ST-1];
        debug("%d %d\n", ans.ST, ans.ND);
        printf("%d\n", ans.ND);
    }
    return 0;
}
void FloydWarshall(){
    for(int kx = 0 ; kx < N; ++kx){
        for(int ky = 0; ky < N; ++ky){
            for(int ix = 0 ; ix < N ; ++ix){
                for(int iy = 0 ; iy < N ; ++iy){
                    for(int jx = 0 ; jx < N ; ++jx){
                        for(int jy = 0 ; jy < N ; ++jy){
                            path[iy][ix][jy][jx].ST = min(path[iy][ix][jy][jx].ST, path[iy][ix][ky][kx].ST + path[ky][kx][jy][jx].ST - grid[ky][kx]);
                        }
                    }
                }
            }
        }
    }
    for(int kx = 0 ; kx < N; ++kx){
        for(int ky = 0; ky < N; ++ky){
            for(int ix = 0 ; ix < N ; ++ix){
                for(int iy = 0 ; iy < N ; ++iy){
                    for(int jx = 0 ; jx < N ; ++jx){
                        for(int jy = 0 ; jy < N ; ++jy){
                            path[iy][ix][jy][jx].ND = min(path[iy][ix][jy][jx].ND, path[iy][ix][ky][kx].ST + path[ky][kx][jy][jx].ST - 2 * grid[ky][kx]);
                        }
                    }
                }
            }
        }
    }
}
void Init(){
    // (ix, iy) => (jx, jy)
    for(int ix = 0; ix < N; ++ix)
        for(int iy = 0 ; iy < N ; ++iy)
            for(int jx = 0 ; jx < N ; ++jx)
                for(int jy = 0 ; jy < N; ++jy){
                    path[iy][ix][jy][jx].ST = path[iy][ix][jy][jx].ND = INF;
                    if(ix == jx && iy == jy){
                        path[iy][ix][jy][jx].ST = grid[iy][ix];
                        path[iy][ix][jy][jx].ND = 0;
                    }
                    if(abs(iy-jy)+abs(ix-jx) == 1){
                        path[iy][ix][jy][jx].ST = grid[iy][ix] + grid[jy][jx];
                        path[iy][ix][jy][jx].ND = min(grid[jy][jx], grid[iy][ix]);
                    }
                }
}