/*********************************************************************
    > File Name: 7.cpp
    > Author: yuki
 *********************************************************************/

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

struct node
{
    int x, y;
    int num;
};

int n, m, k;
node mosq[10];
vector<int> mp[1005][1005];
bool vis[1005][1005];

int step(int x, int y, int xx, int yy)
{
    int res=fabs(x-xx)+fabs(y-yy);
    return res;
}

bool check(int now)
{
    int num[10]={0};
    for(int i=1; i<=k; i++) num[i]=mosq[i].num;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=m; j++)
        {
            mp[i][j].clear();
            vis[i][j]=0;
            for(int id=1; id<=k; id++)
                if(step(i, j, mosq[id].x, mosq[id].y) <= now)
                    mp[i][j].push_back(id);
        }
    for(int id=1; id<=k; id++)
        for(int i=1; i<=n; i++)
            for(int j=1; j<=m; j++)
            {
                if(mp[i][j].size()==0 && !vis[i][j]) return false;
                for(int q=0; q<(int)mp[i][j].size(); q++)
                {
                    int tmp=mp[i][j][q];
                    while(!num[tmp])
                    {
                        swap(mp[i][j][q], mp[i][j].back());
                        mp[i][j].pop_back();
                        if(q >= (int)mp[i][j].size()) break;
                        tmp=mp[i][j][q];
                    }
                }
                if(mp[i][j].size() == 1)
                {
                    int tmp=mp[i][j][0];
                    if(num[tmp] == 0) return false;
                    num[tmp]--;
                    mp[i][j].pop_back();
                    vis[i][j]=1;
                }
            }
    return true;
}

int main()
{
    int t;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d%d%d", &n, &m, &k);
        int tot=0;
        memset(mosq, 0, sizeof(mosq));
        for(int i=1; i<=k; i++)
        {
            scanf("%d%d%d", &mosq[i].x, &mosq[i].y, &mosq[i].num);
            tot+=mosq[i].num;
        }
        if(tot < n*m)
        {
            printf("-1\n");
            continue;
        }
        int l=1, r=n+m;
        int ans=INT_MAX;
        while(l <= r)
        {
            int mid=(l+r)>>1;
            if(check(mid))
            {
                ans=min(ans, mid);
                r=mid-1;
            }
            else l=mid+1;
        }
        printf("%d\n", ans);
    }
    return 0;
}