#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <cstring>
#include <deque>
#include <stack>
#include <stdio.h>
#include <map>
#include <set>
#include <time.h>
#include <string>
#include <fstream>
#include <queue>
#include <bitset>
#include <cstdlib>
#define X first
#define Y second
#define mp make_pair
#define pb push_back
#define pdd pair<double,double>
#define pii pair<ll,ll>
#define PI 3.14159265358979323846
#define MOD 1000000007
#define MOD2 1000000009
#define INF ((ll)1e+18)
#define x1 fldgjdflgjhrthrl
#define x2 fldgjdflgrtyrtyjl
#define y1 fldggfhfghjdflgjl
#define y2 ffgfldgjdflgjl
#define N 500500
#define SUM 23423
#define MAG 1048576
#define OPEN 0
#define CLOSE 1
typedef long long ll;
typedef long double ld;
using namespace std;
ll i,j,n,k,l,m,x,y,tot, flag,h,r,ans,z, K,x1,y1,x2,y2;
string s;
vector<vector<ll> > a;
vector<vector<ll> > t;
vector<pii> scol[1005000];
ll dir[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};
bool good(ll x, ll y, ll val)
{
	if (x < 0 || x >= n || y < 0 || y >= m)
	   return false;
	if (val == (a[x][y]&(MAG-1)))
	   return true;
	return false;
}
void dfs(ll x, ll y, ll col)
{
	if (a[x][y] == col)
	   return;
	a[x][y] = col;
	scol[col].push_back(mp(x,y));
	for (int i = 0; i < 4; i++)
		if (good(x+dir[i][0], y+dir[i][1], 1))
		   dfs(x+dir[i][0], y+dir[i][1], col);
}
void print()
{
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
			cout << a[i][j] << " ";
		cout << endl;
	}
}
bool cmp(pii x1, pii x2)
{
	return t[x1.X][x1.Y] > t[x2.X][x2.Y];
}
int main() {
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	ll tests;
	cin >> tests;
	while (tests--)
	{
		cin >> n >> m >> x >> k;
		a.clear();
		t.clear();
		a.resize(n);
		for (i = 0; i < n; i++)
			a[i].resize(m);
		t.resize(n+1);
		for (i = 0; i < n+1; i++)
			t[i].resize(m+1);
		for (i = 0; i < x; i++)
		{
			cin >> x1 >> y1 >> x2 >> y2;
			if (n<m)
			{
			   for (j = x1; j <= x2; j++)
			   {
				   t[j][y1]++;
				   t[j][y2+1]--;
			   }
			} else
			{
				for (j = y1; j <= y2; j++)
				{
					t[x1][j]++;
					t[x2+1][j]--;
				}
			}
		}
		if (n < m)
		{
			for (i = 0; i < n; i++)
			{
				ll sum = 0;
				for (j = 0; j < m; j++)
				{
					sum += t[i][j];
					a[i][j] = sum;
				}
			}
		} else
		{
			for (j = 0; j < m; j++)
			{
				ll sum = 0;
				for (i = 0; i < n; i++)
				{
					sum += t[i][j];
					a[i][j] = sum;
				}
			}
		}
		for (i = 0; i < n; i++)
		{
			for (j = 0; j < m; j++)
				if (a[i][j] >= k)
				   a[i][j] = 1;
				else
					a[i][j] = 0;
		}
		ll starting_color = 2;
		for (i = 0; i < n; i++)
			for (j = 0; j < m; j++)
				if (a[i][j] == 1)
				{
					scol[starting_color].clear();
					dfs(i,j,starting_color);
					starting_color++;
				}
		/*for (i = 0; i < n; i++)
		{
			for (j = 0; j < m; j++)
				cout << a[i][j];
			cout << endl;
		}*/
		ll ans = 0;
		for (i = 2; i < starting_color; i++)
		{
			ll sum = 0;
			for (j = 0; j < scol[i].size(); j++)
			{
				x = scol[i][j].X, y = scol[i][j].Y;
				if (a[x][y] > MAG)
				   continue;
				sum++;
				if (!good(x-1,y,i) && !good(x+1,y,i))
				{
					a[x][y] += MAG;
					k = y;
					while (good(x,k+1,i))
					{
						k++;
						a[x][k] += MAG;
					}
					k = y;
					while (good(x,k-1,i))
					{
						k--;
						a[x][k] += MAG;
					}
				} else
				if (!good(x,y-1,i) && !good(x,y+1,i))
				{
					a[x][y] += MAG;
					k = x;
					while (good(k+1,y,i))
					{
						k++;
						a[k][y] += MAG;
					}
					k = x;
					while (good(k-1,y,i))
					{
						k--;
						a[k][y] += MAG;
					}
				} else
				sum--;
				//print();
			}
			ans += sum;
			sum = 0;
			for (j = 0; j < scol[i].size(); j++)
			{
				x = scol[i][j].X, y = scol[i][j].Y;
				if (a[x][y] > MAG)
				   continue;
				ll tmp1 = 0, tmp2 = 0;
				k = y;
				while (good(x,k+1,i))
				{
					k++;
					if (a[x][k] == i)
					   tmp1++;
				}
				k = y;
				while (good(x,k-1,i))
				{
					k--;
					if (a[x][k] == i)
					   tmp1++;
				}
				k = x;
				while (good(k+1,y,i))
				{
					k++;
					if (a[k][y] == i)
					   tmp2++;
				}
				k = x;
				while (good(k-1,y,i))
				{
					k--;
					if (a[k][y] == i)
					   tmp2++;
				}
				t[x][y] = max(tmp1, tmp2);
			}
			sort(scol[i].begin(), scol[i].end(), cmp);
			for (j = 0; j < scol[i].size(); j++)
			{
				x = scol[i][j].X, y = scol[i][j].Y;
				if (a[x][y] > MAG)
				   continue;
				sum++;
				a[x][y] += MAG;
				ll tmp1 = 0, tmp2 = 0;
				k = y;
				while (good(x,k+1,i))
				{
					k++;
					if (a[x][k] == i)
					   tmp1++;
				}
				k = y;
				while (good(x,k-1,i))
				{
					k--;
					if (a[x][k] == i)
					   tmp1++;
				}

				k = x;
				while (good(k+1,y,i))
				{
					k++;
					if (a[k][y] == i)
					   tmp2++;
				}
				k = x;
				while (good(k-1,y,i))
				{
					k--;
					if (a[k][y] == i)
					   tmp2++;
				}
				if (tmp1 > tmp2)
				{
					k = y;
					while (good(x,k+1,i))
					{
						k++;
						a[x][k] += MAG;
					}
					k = y;
					while (good(x,k-1,i))
					{
						k--;
						a[x][k] += MAG;
					}
				} else
				{
					k = x;
					while (good(k+1,y,i))
					{
						k++;
						a[k][y] += MAG;
					}
					k = x;
					while (good(k-1,y,i))
					{
						k--;
						a[k][y] += MAG;
					}
				}
			}
			ans += sum;
		}
		cout << ans << endl;
	}
	return 0;
}