#include <iostream>#include <cstring>#include <cstdio>#include <cmath>#include <vector>using namespace std;#define FOR(i,A,s)  for(int i = A[s]; i != s; i = A[i])#define exp 1e-8const int MAX = 510000;int n, m, k, t, len;struct DLX {    int n, Size;//Size为尾指针，真正大小    int row[MAX], col[MAX];//记录每个点的行列    int U[MAX], D[MAX], R[MAX], L[MAX]; //4个链表    int S[MAX],H[MAX];//每列1的个数    int ncnt, ans[MAX];    void init (int n) {        this->n = n;        ncnt = MAX;        //增加n+1个辅助链表，从0到n        for (int i = 0; i <= n; i++)            U[i] = D[i] = i, L[i] = i - 1, R[i] = i + 1,S[i]=0;        R[n] = 0, L[0] = n; //头尾相接        Size = n + 1;        memset (H, -1, sizeof H);    }    //单点添加    void Link (int r, int c)    {        ++S[col[++Size] = c];        row[Size] = r;        D[Size] = D[c];        U[D[c]] = Size;        U[Size] = c;        D[c] = Size;        if (H[r] < 0) H[r] = L[Size] = R[Size] = Size;        else        {            R[Size] = R[H[r]];            L[R[H[r]]] = Size;            L[Size] = H[r];            R[H[r]] = Size;        }    }    void Remove (int c) {        //精确覆盖        L[R[c]] = L[c], R[L[c]] = R[c];        FOR (i, D, c)        FOR (j, R, i)        U[D[j]] = U[j], D[U[j]] = D[j], --S[col[j]];//        //重复覆盖//        for (int i = D[c]; i != c; i = D[i])//            L[R[i]] = L[i], R[L[i]] = R[i];    }    void Restore (int c) {        FOR (i, U, c)        FOR (j, L, i)        ++S[col[j]], U[D[j]] = j, D[U[j]] = j;        L[R[c]] = c, R[L[c]] = c;        //重复覆盖//        for (int i = U[c]; i != c; i = U[i])//            L[R[i]] = R[L[i]] = i;    }    bool v[MAX];    int ff() {        int ret = 0;        for (int c = R[0]; c != 0; c = R[c]) v[c] = true;        for (int c = R[0]; c != 0; c = R[c])            if (v[c])            {                ret++;                v[c] = false;                for (int i = D[c]; i != c; i = D[i])                    for (int j = R[i]; j != i; j = R[j])                        v[col[j]] = false;            }        return ret;    }    bool dfs (int d) {        if (d >= ncnt) return 0;        //if (d + ff() > k) return 0;//重复覆盖        if (R[0] == 0) {            ncnt = min (ncnt, d);            return 1;        }        int c = R[0];        for (int i = R[0]; i != 0; i = R[i])            if (S[i] < S[c])                c = i;        Remove (c);//精确覆盖        FOR (i, D, c) {            //Remove (i);//重复覆盖            ans[d] = row[i];            FOR (j, R, i) Remove (col[j]);//精确覆盖            //FOR (j, R, i) Remove (j);//重复覆盖            //if (dfs (d + 1) ) return 1;            dfs (d + 1);            FOR (j, L, i) Restore (col[j]);//精确覆盖            //FOR (j, L, i) Restore (j);//重复覆盖            //Restore (i);//重复覆盖        }        Restore (c);//精确覆盖        return 0;    }    bool solve (vector<int> &v) {        v.clear();        if (!dfs (0) ) return 0;        for (int i = 0; i < ncnt; i++) v.push_back (ans[i]);        return 1;    }} Dance;int columns[31][31 * 31];int main() {    scanf ("%d", &t);    while (t--) {        memset (columns, 0, sizeof columns);        scanf ("%d %d %d", &n, &m, &k);        len = n * m;        Dance.init (len);        int x,y,xx,yy;        for (int p = 1; p <= k; p++) {            scanf ("%d %d %d %d", &x, &y, &xx, &yy);            for (int i = x+1; i <= xx; i++)                for (int j = y+1; j <= yy; j++)                    Dance.Link (p, j + (i-1)*m);        }        Dance.dfs (0);        printf ("%d\n", Dance.ncnt == MAX ? -1 : Dance.ncnt);    }    return 0;}