#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <queue>
#include <cstring>

using namespace std;

#define sz size()
#define pb push_back
#define len length()
#define clr clear()
#define FOR(i,a,b) for(i=a;i<b;i++)
#define FORR(i,n) for(i=0;i<n;i++)
#define is_digit(c) ('0'<=(c) && (c)<='9')

#define eps 0.0000001
#define PI  3.14159265359
#define inf 1999888777

int ans[1005][1005];

struct polje {
    int v,x,y;
} a[1000555];

bool cmp(polje a, polje b) {
    return (a.v < b.v);
}

int dist(int x1, int y1, int x2, int y2) {
    return (abs(x1-x2) + abs(y1-y2));
}

int main() {

    FILE *fin = fopen("pentranje.in", "r"), *fout = fopen("pentranje.out", "w");

    int n,i,j,x,y,q,pi,qi,up,ux[5],uy[5],ugx[5],ugy[5];

    fscanf(fin, "%d", &n);
    for(i=0; i<n; i++) {
        for(j=0; j<n; j++) {
            fscanf(fin,"%d", &a[i*n+j].v);
            a[i*n+j].x = i;
            a[i*n+j].y = j;
        }
    }

    sort(a,a+n*n,cmp);

    ugx[0] = 0; ugy[0] = 0;
    ugx[1] = 0; ugy[1] = n-1;
    ugx[2] = n-1; ugy[2] = 0;
    ugx[3] = n-1; ugy[3] = n-1;

    ans[a[0].x][a[0].y] = -1;
    for(j=0; j<4; j++) {
        ux[j] = a[0].x; uy[j] = a[0].y;
    }

    i=1;
    while(i<n && a[i].v == a[i-1].v) {
        ans[a[i].x][a[i].y] = -1;

        for(j=0; j<4; j++) {
            if ( dist(a[i].x,a[i].y,ugx[j],ugy[j]) < dist(ux[j], uy[j], ugx[j], ugy[j]) ) {
                ux[j] = a[i].x;
                uy[j] = a[i].y;
            }
        }
        i++;
    }

    while(i<n*n) {

        pi = i;
        do {
            ans[a[i].x][a[i].y] = 0;
            for(j=0; j<4; j++) {
                ans[a[i].x][a[i].y] = max(ans[a[i].x][a[i].y], dist(a[i].x,a[i].y,ux[j],uy[j]));
            }

            i++;
        } while(i<n*n && a[i].v == a[i-1].v);

        for(qi=pi; qi<i; qi++) {
            for(j=0; j<4; j++) {
                if ( dist(a[qi].x,a[qi].y,ugx[j],ugy[j]) < dist(ux[j], uy[j], ugx[j], ugy[j]) ) {
                    ux[j] = a[qi].x;
                    uy[j] = a[qi].y;
                }
            }
        }
    }

    fscanf(fin,"%d", &q);
    for(i=0; i<q; i++) {
        fscanf(fin,"%d%d%d", &up, &x, &y);
        fprintf(fout, "%d\n", ans[x-1][y-1]);
    }

    fclose(fin); fclose(fout);

    return 0;
}