# include<cstdio>

# include<cstring>

# include<algorithm>

using namespace std;

# define lson l,m,rt<<

# define rson m+,r,rt<<|

# define MAXN

int xL,xR,yL,yR,val;

int maxv,minv;

int Max[MAXN<<][MAXN<<],Min[MAXN<<][MAXN<<];

int N,mat[MAXN][MAXN];

void PushUp(int xrt,int rt)

{

    Max[xrt][rt]=max(Max[xrt][rt<<],Max[xrt][rt<<|]);

    Min[xrt][rt]=min(Min[xrt][rt<<],Min[xrt][rt<<|]);

}

void BuildY(int xrt,int x,int l,int r,int rt)

{

    int m;

    if(l==r)

    {

        if(x!=-) Max[xrt][rt]=Min[xrt][rt]=mat[x][l];

        else

        {

            Max[xrt][rt]=max(Max[xrt<<][rt],Max[xrt<<|][rt]);

            Min[xrt][rt]=min(Min[xrt<<][rt],Min[xrt<<|][rt]);

        }

        return;

    }

    m=(l+r)>>;

    BuildY(xrt,x,lson);

    BuildY(xrt,x,rson);

    PushUp(xrt,rt);

}

void BuildX(int l,int r,int rt)

{

    int m;

    if(l==r)

    {

        BuildY(rt,l,,N,);

        return;

    }

    m=(l+r)>>;

    BuildX(lson);

    BuildX(rson);

    BuildY(rt,-,,N,);

}

void UpdateY(int xrt,int x,int l,int r,int rt)

{

    int m;

    if(l==r)

    {

        if(x!=-) Max[xrt][rt]=Min[xrt][rt]=val;

        else

        {

            Max[xrt][rt]=max(Max[xrt<<][rt],Max[xrt<<|][rt]);

            Min[xrt][rt]=min(Min[xrt<<][rt],Min[xrt<<|][rt]);

        }

        return;

    }

    m=(l+r)>>;

    if(yL<=m) UpdateY(xrt,x,lson);

    else UpdateY(xrt,x,rson);

    PushUp(xrt,rt);

}

void UpdateX(int l,int r,int rt)

{

    int m;

    if(l==r)

    {

        UpdateY(rt,l,,N,);

        return;

    }

    m=(l+r)>>;

    if(xL<=m) UpdateX(lson);

    else UpdateX(rson);

    UpdateY(rt,-,,N,);

}

void QueryY(int xrt,int l,int r,int rt)

{

    int m;

    if(yL<=l&&yR>=r)

    {

        minv=min(minv,Min[xrt][rt]);

        maxv=max(maxv,Max[xrt][rt]);

        return;

    }

    m=(l+r)>>;

    if(yL<=m) QueryY(xrt,lson);

    if(yR>m) QueryY(xrt, rson);

}

void QueryX(int l,int r,int rt)

{

    int m;

    if(xL<=l&&xR>=r)

    {

        QueryY(rt,,N,);

        return;

    }

    m=(l+r)>>;

    if(xL<=m) QueryX(lson);

    if(xR>m) QueryX(rson);

}

int main()

{

    //freopen("in.txt","r",stdin);

    int i,j,q,cas,T,x,y,l;

    char op[];

    scanf("%d",&T);

    for(cas=;cas<=T;cas++)

    {

        scanf("%d",&N);

        for(i=;i<=N;i++)

            for(j=;j<=N;j++)

                scanf("%d",&mat[i][j]);

        BuildX(,N,);

        scanf("%d",&q);

        printf("Case #%d:\n",cas);

        while(q--)

        {

            scanf("%d%d%d",&x,&y,&l);

            l=(l+)/;

            xL=max(,x-l+),xR=min(N,x+l-);

            yL=max(,y-l+),yR=min(N,y+l-);

            minv=<<,maxv=-(<<);

            QueryX(,N,);

            val=(maxv+minv)/;

            xL=x,yL=y;

            printf("%d\n",val);

            UpdateX(,N,);

        }

    }

    return ;

}