#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <vector>using namespace std;const int maxn=920;const int maxnode=920*550;const int maxr=550;int ans;struct DLX{  int n , sz;                                                 // 行数，节点总数  int S[maxn];                                                // 各列节点总数  int row[maxnode],col[maxnode];                              // 各节点行列编号  int L[maxnode],R[maxnode],U[maxnode],D[maxnode];            // 十字链表   int ansd;                                         // 解   void init(int n )  {    this->n = n ;    for(int i = 0 ; i <= n; i++ )    {      U[i] = i ;      D[i] = i ;      L[i] = i - 1;      R[i] = i + 1;    }    R[n] = 0 ;    L[0] = n;    sz = n + 1 ;    memset(S,0,sizeof(S));  }  void addRow(int r,vector<int> c1)  {    int first = sz;    for(int i = 0 ; i < c1.size(); i++ ){      int c = c1[i];      L[sz] = sz - 1 ; R[sz] = sz + 1 ; D[sz] = c ; U[sz] = U[c];      D[U[c]] = sz; U[c] = sz;      row[sz] = r; col[sz] = c;      S[c] ++ ; sz ++ ;    }    R[sz - 1] = first ; L[first] = sz - 1;  }  // 顺着链表A，遍历除s外的其他元素  #define FOR(i,A,s) for(int i = A[s]; i != s ; i = A[i])   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]];}  }  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;  }  void dfs(int d){  	if(d>=ans) return ;    if(R[0] == 0 ){      ansd = d;      ans=min(ans,ansd);    }    // 找S最小的列c    int c = R[0] ;    FOR(i,R,0) if(S[i] < S[c]) c = i;     remove(c);    FOR(i,D,c){      FOR(j,R,i) remove(col[j]);      dfs(d + 1);      FOR(j,L,i) restore(col[j]);    }    restore(c);  }  bool solve(){    dfs(0);  }};DLX solver;int main(){	int T; int n,m ,p; int xx1,xx2,yy1,yy2;	vector<int>colmuns;	scanf("%d",&T);	while(T--){		ans=(1<<30);		scanf("%d%d%d",&n,&m,&p);		solver.init(n*m);		for(int k=1;k<=p;k++){			colmuns.clear();			scanf("%d%d%d%d",&xx1,&yy1,&xx2,&yy2);			for(int i=xx1+1;i<=xx2;i++){				for(int j=yy1+1;j<=yy2;j++){					colmuns.push_back((i-1)*m+j);				}			}			solver.addRow(k,colmuns);		}		solver.solve();		if(ans==(1<<30)) printf("-1\n");		else printf("%d\n",ans);	}	return 0;}