#include<bits/stdc++.h> #define up(i,l,r) for(int i=(l);i<=(r);++i) #define down(i,l,r) for(int i=(l);i>=(r);--i) #define pi pair<int,int> #define p1 first #define p2 second #define m_p make_pair #define pb push_back #define eb emplace_back using namespace std; typedef long long ll; inline ll read(){ ll x=0;short t=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')t=-1;ch=getchar();} while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar(); return x*t; } int n,m,k; vector<int>vis[2005],mark[2005],tag[2005],ok[2005],reach[2005]; const int dx[]={1,-1,0,0},dy[]={0,0,1,-1}; bool chk(int x){ up(i,1,n)up(j,1,m)tag[i][j]=ok[i][j]=reach[i][j]=0; int u=-1,v=-1; up(i,1,n-x+1)up(j,1,m-x+1){ int w=vis[i+x-1][j+x-1]-vis[i+x-1][j-1]-vis[i-1][j+x-1]+vis[i-1][j-1]; if(!w)ok[i][j]=1,u=i,v=j,tag[i][j]++,tag[i][j+x]--,tag[i+x][j]--,tag[i+x][j+x]++; } up(i,1,n)up(j,1,m)tag[i][j]+=tag[i-1][j]; up(i,1,n)up(j,1,m)tag[i][j]+=tag[i][j-1]; up(i,1,n)up(j,1,m)if((!mark[i][j])&&(!tag[i][j]))return 0; queue<pi>q;q.push({u,v});reach[u][v]=1; while(!q.empty()){ auto [x,y]=q.front();q.pop(); up(j,0,3){ int nx=x+dx[j],ny=y+dy[j]; if(nx<1||nx>n||ny<1||ny>m)continue; if((!ok[nx][ny])||reach[nx][ny])continue; reach[nx][ny]=1,q.push({nx,ny}); } } up(i,1,n)up(j,1,m)if(ok[i][j]&&(!reach[i][j]))return 0; return 1; } void slv(){ n=read(),m=read(),k=read(); bool F=0;if(n>m)F=1,swap(n,m); up(i,0,n+1){ vis[i].clear(),vis[i].resize(m+2,0); tag[i].clear(),tag[i].resize(m+2,0); ok[i].clear(),ok[i].resize(m+2,0); reach[i].clear(),reach[i].resize(m+2,0); mark[i].clear(),mark[i].resize(m+2,0); } up(i,1,k){int x=read(),y=read();if(F)swap(x,y);vis[x][y]=mark[x][y]=1;} up(i,1,n)up(j,1,m)vis[i][j]+=vis[i][j-1]; up(i,1,n)up(j,1,m)vis[i][j]+=vis[i-1][j]; if(!chk(1))return puts("-1"),void(); int l=1,r=min(n,m)+1; while(l+1<r){ int mid=l+r>>1; if(chk(mid))l=mid; else r=mid; } printf("%d\n",l); } int main(){ //freopen("meet.in","r",stdin),freopen("meet.out","w",stdout); int c=read(),t=read();while(t--)slv(); return 0; }