#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long int

ll read(){
    char ch=getchar();
    ll sum=0;
    bool ttt=false;
    while(!isdigit(ch)) ttt=(ch=='-'),ch=getchar();
    while(isdigit(ch)) sum=(sum<<3)+(sum<<1)+(ch-'0'),ch=getchar();
    return ttt?-sum:sum;
}

int tst;
int n,m,k;

int x[10],y[10],z[10];

int dv(int x, int y){
    if(x%y) return x/y+1;
    return x/y;
}

int dd(int x1,int y1,int x2,int y2){
    int dx=abs(x1-x2),dy=abs(y1-y2);
    return dx+dy;
}

int sum[110],tmp[110];
const int v[8]={0,1,2,4,8,16,32,64};
int a[1010][1010];
bool pd(int dis){
    memset(a,0,sizeof(a));
    memset(tmp,0,sizeof(tmp));
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            for(int p=1;p<=k;p++){
                if(dd(i,j,x[p],y[p])<=dis) a[i][j]+=v[p];
            }
            if(!a[i][j]) return false;
            tmp[a[i][j]]++;
        }
    }
    for(int i=1;i<v[k+1];i++) if(tmp[i]>sum[i]) return false;
    return true;
}

int main(){
    tst=read();
    for(int i=1;i<=tst;i++){
        memset(sum,0,sizeof(sum));
        int tt=0;
        n=read(),m=read(),k=read();
        for(int i=1;i<=k;i++) x[i]=read(),y[i]=read(),z[i]=read(),tt+=z[i];
        if(tt<n*m){
            puts("-1");
            continue;
        }
        
        for(int i=1;i<v[k+1];i++){
            for(int j=1;j<=k;j++){
                if(i&v[j]) sum[i]+=z[j];
            }
        }
        
        int l=0,r=n+m;
        while(l<=r){
            int mid=(l+r)>>1;
            if(pd(mid)) r=mid-1;
            else l=mid+1;
        }
        printf("%d\n",r+1);
    }
    return 0;
}