//     自己选择的路，跪着也要走完。朋友们，虽然这个世界日益浮躁起来，只
// 要能够为了当时纯粹的梦想和感动坚持努力下去，不管其它人怎么样，我们也
// 能够保持自己的本色走下去。                               ――陈立杰
/*************************************
 * @contest:      2020 年百度之星・程序设计大赛 - 初赛一.
 * @user_name:    brealid/hkxadpall/zhaoyi20/jmoo/jomoo/航空信奥/littleTortoise.
 * @time:         2020-07-19.
 * @language:     C++.
*************************************/ 

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

typedef signed char          int8;
typedef unsigned char       uint8;
typedef short                int16;
typedef unsigned short      uint16;
typedef int                  int32;
typedef unsigned            uint32;
typedef long long            int64;
typedef unsigned long long  uint64;

namespace baseFastio {
    template <typename Int>
    inline Int read()       
    {
        Int flag = 1;
        char c = getchar();
        while ((!isdigit(c)) && c != '-' && c != EOF) c = getchar();
        if (c == '-') flag = -1, c = getchar();
        Int init = c & 15;
        while (isdigit(c = getchar())) init = (init << 3) + (init << 1) + (c & 15);
        return init * flag;
    }

    template <typename Int>
    inline Int read(char &c)       
    {
        Int flag = 1;
        c = getchar();
        while ((!isdigit(c)) && c != '-' && c != EOF) c = getchar();
        if (c == '-') flag = -1, c = getchar();
        Int init = c & 15;
        while (isdigit(c = getchar())) init = (init << 3) + (init << 1) + (c & 15);
        return init * flag;
    }

    template <typename Int>
    inline void write(Int x)
    {
        if (x < 0) putchar('-'), x = ~x + 1;
        if (x > 9) write(x / 10);
        putchar((x % 10) | 48);
    }  

    template <typename Int>
    inline void write(Int x, char nextch)
    {
        write(x);
        putchar(nextch);
    }
}

namespace Fastio {
    enum io_flags {
        ignore_int = 1 << 0
    };

    struct Reader {
        char endch;
        Reader() { endch = '\0'; }
        template <typename Int>
        Int operator () () {
            return baseFastio::read<Int>(endch);;
        }
        Reader& operator >> (io_flags f) {
            if (f == ignore_int) baseFastio::read<int>();
            return *this;
        }
        template <typename Int>
        Reader& operator >> (Int &i) {
            i = baseFastio::read<Int>(endch);
            return *this;
        }
        template <typename Int>
        inline Int get_int() {
            return baseFastio::read<Int>();
        }
        inline char get_nxt() {
            return endch;
        }
    } read;

    struct Writer {
        Writer& operator << (const char *ch) {
            // char *p = ch;
            while (*ch) putchar(*(ch++));
            return *this;
        }
        Writer& operator << (const char ch) {
            putchar(ch);
            return *this;
        }
        template <typename Int>
        Writer& operator << (const Int i) {
            baseFastio::write(i);
            return *this;
        }
    } write;
}
using namespace Fastio;

// #define int int64

int n, m, k;
int x[6], y[6], z[6];
int a[1007][1007];

int thek[64];
int popcount[64] = {0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 
                    1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6};

bool check(int tim) {
    int need[64] = {0};
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            a[i][j] = 0;
            for (int g = 0; g < k; g++) 
                if (abs(x[g] - i) + abs(y[g] - j) <= tim)
                    a[i][j] |= (1 << g);
            if (!a[i][j]) return false;
            else need[a[i][j]]++;
        }
    for (int i = 0; i < 64; i++) {
        int total_need = 0, total_have = 0;
        for (int k = 0; k < 64; k++) {
            if (!(k & (~i))) total_need += need[k];
        }
        int tmp = i;
        while (tmp) {
            total_have += z[thek[tmp & -tmp]];
            tmp -= tmp & -tmp;
        }
        if (total_need > total_have) return false;
    }
    return true;
}

void solve() {
    read >> n >> m >> k;
    for (int i = 0; i < k; i++) {
        read >> x[i] >> y[i] >> z[i];
    }
    int l = 0, r = n + m + 3, mid, ans = -1;
    while (l <= r) {
        mid = (l + r) >> 1;
        if (check(mid)) r = mid - 1, ans = mid;
        else l = mid + 1;
    }
    write << ans << '\n';
}

signed main() {
    thek[1] = 0;
    thek[2] = 1;
    thek[4] = 2;
    thek[8] = 3;
    thek[16] = 4;
    thek[32] = 5;
    int T = baseFastio::read<int>();
    while (T--) solve();
    return 0;
}