#include<bits/stdc++.h>
using namespace std;
int vis[6000005],vis2[6000005];
int vis1[6000005];
int dont[6000005];
int id,T,n,m,k,a[6000006],b[6000005],cnt;
int v[]={0,0,1,-1},s[]={1,-1,0,0};
int l,r,mid,ans,w;
int pos(int x,int y)
{
    if(x==0||y==0) return 0;
    return (x-1)*m+y;
}
int qsum(int x,int y,int xx,int yy)
{
    return dont[pos(xx,yy)]-dont[pos(x-1,yy)]-dont[pos(xx,y-1)]+dont[pos(x-1,y-1)];
}
int qsum1(int x,int y,int xx,int yy)
{
    return vis1[pos(xx,yy)]-vis1[pos(x-1,yy)]-vis1[pos(xx,y-1)]+vis1[pos(x-1,y-1)];
}
void dfs(int x,int y)
{
    cnt++;vis[pos(x,y)]=1;
    for(int i=0;i<4;i++)
    {
        int q=x+v[i],p=y+s[i];
        if(q>=1&&q<=n&&p>=1&&p<=m&&vis[pos(q,p)]==0)
        dfs(q,p);
    }
}
void make_dont()
{
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        dont[pos(i,j)]=dont[pos(i,j)]+dont[pos(i-1,j)]+dont[pos(i,j-1)]-dont[pos(i-1,j-1)];
    }
}
void make_vis1()
{
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        vis1[pos(i,j)]=vis1[pos(i,j)]+vis1[pos(i-1,j)]+vis1[pos(i,j-1)]-vis1[pos(i-1,j-1)];
    }
}
bool check1()
{
    cnt=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(vis[pos(i,j)]==0)
            {cnt=0;dfs(i,j);break;}
        }
        if(cnt!=0) break;
    }return cnt==(n*m-k);
}
void dfs2(int x,int y)
{
    w++;vis2[pos(x,y)]=1;
    for(int i=0;i<4;i++)
    {
        int q=x+v[i],p=y+s[i];
        if(q>=1&&q<=n&&p>=1&&p<=m&&qsum1(q,p,q,p)==1&&vis2[pos(q,p)]==0)
        dfs2(q,p);
    }
}
bool check(int x)
{
    for(int i=0;i<=3000000;i++) {vis1[i]=0;vis2[i]=0;}
    int fx=0,fy=0;cnt=0;
    for(int i=1;i+x-1<=n;i++)
    {
        for(int j=1;j+x-1<=m;j++)
        {
            if(qsum(i,j,i+x-1,j+x-1)==0)
            {    
                vis1[pos(i,j)]=1;cnt++;fx=i;fy=j;
            }
        }
    }
    if(cnt==0) return 0;
    make_vis1();
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(qsum(i,j,i,j)==0&&qsum1(max(1,i-x+1),max(1,j-x+1),i,j)==0)
            return 0;
        }
    }
    w=0;dfs2(fx,fy);
    if(w==cnt) return 1;
    return 0;
}
void init()
{
    for(int i=0;i<=3000000;i++)
    {dont[i]=0;vis[i]=0;}
}
int main()
{
    // freopen("meet2.in","r",stdin);
    // freopen("meet.out","w",stdout);
    scanf("%d%d",&id,&T);
    while(T--)
    {
        init();
        scanf("%d%d%d",&n,&m,&k);
        for(int i=1;i<=k;i++) {scanf("%d%d",&a[i],&b[i]);dont[pos(a[i],b[i])]=1;vis[pos(a[i],b[i])]=1;}
        if(check1()==0) {printf("-1\n");continue;}
        make_dont();
        l=1;r=n;ans=-1;
        while(l<=r)
        {
            mid=(l+r)>>1;
            if(check(mid)) {ans=mid;l=mid+1;}
            else r=mid-1;
        }printf("%d\n",ans);
    }
    return 0;
}