#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll; typedef unsigned long long ull; typedef pair<ll, ll>pi; typedef complex<double>cx;
#define int ll
#define X first
#define Y second
#define fer(i,a,n) for(int i=a;i<=n;i++)
#define ref(i,n,a) for(int i=n;i>=a;i--)
#define endl '\n'
#define mem(a,x) memset(a,x,sizeof a)
#define ac IO;int t;cin>>t;while(t--)solve()
#define AC signed main(){IO;solve();}
#define NO {cout<<"NO"<<endl;return;}
#define YES {cout<<"YES"<<endl;return;}
#define re(a) {cout<<a<<endl;return;}
#define all(v) v.begin(),v.end()
//ofstream fout("1.out", ios::out);
//ifstream fin("1.in", ios::in);
//#define cout fout
//#define cin fin
//--------------------瑞神神中神--------------------

const int N=1e5+10,M=18,K=3;
int a[M][N],f[N][M][K+2],tot[M][N],mx[M][M];
int n,m,q;

int cmp(int i,int x,int y)
{
    if(tot[i][x]<tot[i][y])return 1;
    if(tot[i][x]==tot[i][y])return 0;
    return -1;
}

void solve()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        tot[i][0]=n+1;
        for(int j=1;j<=n;j++)
        {
            cin>>a[i][j];
            tot[i][a[i][j]]=j;
            f[j][i][0]=j;
        }
        for(int k=1;k<=m;k++)
        {
            mx[i][k]=0;
        }
    }
    for(int i=n;i>=1;i--)
    {
        for(int j=1;j<=m;j++)
        {
            for(int k=1;k<=m;k++)   //从k跳向j
            {
                if(cmp(j,mx[k][j],f[a[k][i]][j][0])==1)
                {
                    f[a[k][i]][j][0]=mx[k][j];
                }
            }
        }
        for(int j=1;j<=m;j++)
        {
            for(int k=1;k<=m;k++)
            {
                if(cmp(k,a[j][i],mx[j][k])==1)
                {
                    mx[j][k]=a[j][i];
                }
            }
        }
    }
    for(int k=1;k<=K;k++)
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                f[i][j][k]=f[i][j][k-1];
                for(int l=1;l<=m;l++)
                {
                    int ul=f[i][l][k-1];
                    if(cmp(j,f[ul][j][k-1],f[i][j][k])==1)
                    {
                        f[i][j][k]=f[ul][j][k-1];
                    }
                }
            }
        }
    }
    cin>>q;
    while(q--)
    {
        int x,y;
        cin>>x>>y;
        int flg=0;
        for(int i=1;i<=m;i++)
        {
            if(cmp(i,x,y)==1)
            {
                flg=1;
            }
        }
        if(flg)
        {
            cout<<1<<'\n';
            continue;
        }
        if(m==1)
        {
            cout<<-1<<'\n';
            continue;
        }
        vector<int>p(m+1,x);
        int ans=0;
        for(int k=K;k>=0;k--)
        {
            vector<int>tmp(m+1);
            for(int i=1;i<=m;i++)
            {
                for(int j=1;j<=m;j++)
                {
                    if(cmp(j,f[p[i]][j][k],tmp[j]))
                    {
                        tmp[j]=f[p[i]][j][k];
                    }
                }
            }
            flg=-1;
            for(int i=1;i<=m;i++)
            {
                flg=max(flg,cmp(i,tmp[i],y));
            }
            if(flg==-1)
            {
                ans+=1<<k;
                p=tmp;
            }
            else if(flg==0)
            {
                ans+=1<<k;
                break;
            }
        }
        cout<<ans+2<<'\n';
    }
}

AC