#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
struct solver {
struct node {
    int x, y, z;
    node(int _x = 0, int _y = 0, int _z = 0) {
        x = _x, y = _y, z = _z;
    }
};
int n, s, t, cur[100005], dis[100005];
queue <int> q;
vector <node> a[100005];
bool BFS() {
    memset(dis, 0x3f, sizeof dis);
    while (!q.empty()) q.pop();
    q.push(s); dis[s] = 0;
    while (!q.empty()) {
        int o = q.front(); q.pop();
        int d = dis[o] + 1;
        for (int i = 0; i < (int)a[o].size(); i++)
            if (a[o][i].y > 0 && dis[a[o][i].x] > d) {
                dis[a[o][i].x] = d;
                q.push(a[o][i].x);
            }
    }
    return dis[t] != INF;
}
int DFS(int x, int Min) {
    if (!Min || x == t) return Min;
    int ans = 0, f;
    for (; cur[x] < (int)a[x].size(); cur[x]++) {
        node &e = a[x][cur[x]];
        if (!e.y || dis[x] + 1 != dis[e.x]) continue;
        if ((f = DFS(e.x, min(Min, e.y))) > 0) {
            e.y -= f, a[e.x][e.z].y += f;
            ans += f, Min -= f;
            if (!Min) break;
        }
    }
    return ans;
}
void add_edge(int u, int v, int w) {
    a[u].push_back((node){v, w, (int)a[v].size()});
    a[v].push_back((node){u, 0, (int)a[u].size() - 1});
}
int solve() {
    int ans = 0;
    while (BFS()) {
        memset(cur, 0, sizeof cur);
        int x;
        do x = DFS(s, INF), ans += x;
        while (x);
    }
    return ans;
}
} solver;

int n, m, K;
int x[10], y[10], z[10];
int check(int lim) {
    int cnt[100];
    memset(cnt, 0, sizeof cnt);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            int mask = 0;
            for (int k = 1; k <= K; k++)
                if (abs(i - x[k]) + abs(j - y[k]) <= lim)
                    mask ^= 1 << (k - 1);
            cnt[mask]++;
        }
    solver.s = 1;
    solver.n = solver.t = K + (1 << K) + 2;
    for (int i = 0; i <= solver.n; i++) solver.a[i].clear();
    for (int i = 1; i <= K; i++) solver.add_edge(1, i + 1, z[i]);
    for (int i = 1; i <= (1 << K); i++) solver.add_edge(K + i + 1, solver.t, cnt[i - 1]);
    for (int i = 1; i <= K; i++)
        for (int j = 1; j <= (1 << K); j++) {
            if ((j - 1) & (1 << (i - 1))) solver.add_edge(i + 1, K + j + 1, n * m);
        }
    return solver.solve() == n * m;
}
void solve() {
    cin >> n >> m >> K;
    for (int i = 1; i <= K; i++)
        cin >> x[i] >> y[i] >> z[i];
    int l = 0, r = 2000, ans = -1;
    while (l <= r) {
        int mid = (l + r) / 2;
        if (check(mid)) ans = mid, r = mid - 1;
        else l = mid + 1;
    }
    cout << ans << endl;
}
int main() {
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}