#include <iostream>
#include <fstream>
using namespace std;

#define in cin
//ifstream in("4478.txt");

inline int maxi(int a, int b)
{
    return (a > b) ? a : b;
}

// BÚSQUEDAS BINARIAS //

inline int bb(int a[], int elem, int izq, int der) {
    while (izq <= der) {
        int med = (izq + der) / 2;
        if (a[med] < elem)
            izq = med + 1;
        else
            der = med - 1;
    }
    return izq;
}

inline int bb(int a[500][500], int elem, int izq, int der, int t) {
    while (izq <= der) {
        int med = (izq + der) / 2;
        if (a[med][med+t] <= elem)
            izq = med + 1;
        else
            der = med - 1;
    }
    return der;
}

int main()
{
    int n,m,q,l,u;
    int town[500][500];

    while (in>>n>>m && n!=0)
    {
        for (int i=0; i<n; i++)
            for (int j=0; j<m; j++)
                in>>town[i][j];
        in>>q;

        for (int k=0; k<q; k++)
        {
            in>>l>>u;
            int ladoMax=0;
            for (int i=0; i<n-ladoMax; i++)		// para cada fila O(n)
            {
                int t = bb(town[i], l, 0, m-1);		// busco el menor casillero válido O(logn)
                if (t < 0) break;					// si no lo encuentro corto, tampoco lo voy a encontrar en las siguientes filas
                t -= i;								// calculo la ordenada, para saber la columna a partir de una fila
                int j = bb(town, u, i, (n-1+t < m) ? n-1 : m-1-t, t);	// busco por la diagonal el mayor valor válido max(O(logn),O(logm))
                ladoMax = maxi(ladoMax, j-i+1);		// calculo el lado del cuadrado encontrado y me quedo con el mayor
            }
            cout << ladoMax << endl;
        }
        cout << "-" << endl;
    }
    return 0;
}