#include <bits/stdc++.h>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fod(i,a,b) for(int i=a;i>=b;i--)
#define me0(a) memset(a,0,sizeof(a))
#define me1(a) memset(a,-1,sizeof(a))
#define op freopen("in.txt", "r", stdin)
#define pii pair<int,int>
#define mp(x,y) make_pair(x,y)
using namespace std;
const int INF = 0x3f3f3f3f;
typedef unsigned long long ULL;
typedef long long LL;
void read(int& val) { int x = 0; int bz = 1; char c; for (c = getchar(); (c<'0' || c>'9') && c != '-'; c = getchar()); if (c == '-') { bz = -1; c = getchar(); }for (; c >= '0' && c <= '9'; c = getchar()) x = x * 10 + c - 48; val = x * bz; }
const int mod=1e9+7;
const int maxn=1e6+10;
int n,m,t,k;
int x[maxn],y[maxn],z[maxn];
int num[1100][1100],id[1010][1010][6];

bool check(int mid){
    int t[10];
    fo(i,1,k) t[i]=z[i];

    fo(i,1,n){
        fo(j,1,m){
            num[i][j]=0;
            vector<int>tmp;
            fo(a,1,k){
                if(abs(i-x[a])+abs(j-y[a])<=mid&&t[a]){
                    id[i][j][num[i][j]]=a;num[i][j]++;
                }
            }
            if(num[i][j]==0) return false;
            if(num[i][j]==1){
                t[id[i][j][0]]--;
            }
        }
    }
    return true;
}

int main(){
//    op;
    read(t);
    while(t--){
        read(n);read(m);read(k);
        int sum=0;
        fo(i,1,k) {
            read(x[i]),read(y[i]),read(z[i]),sum+=z[i];
        }
        if(sum<n*m){
            puts("-1");continue;
        }

        int l=1,r=n*m,ans=0;
        while(l<=r){
            int mid=l+r>>1;
            if(check(mid)) {
                r=mid-1,ans=mid;
            }
            else l=mid+1;
        }
        printf("%d\n",ans);
    }
    return 0;
}