#include <iostream>
using namespace std;

const int MAXEDGES = 200;
const int MAXBORDERS = 20;

long perims[MAXBORDERS+1];
long areas[MAXBORDERS+1];
class Edge
{
public:
	int x1, y1, x2, y2;
	int dx1, dx2, dy1, dy2;
	bool isHoriz;
	bool clipped;

	Edge()
	{}

	Edge(int nx1, int nx2, int ny1, int ny2, int d)
	{
		set(nx1, nx2, ny1, ny2, d);
	}

	Edge(int nx1, int nx2, int ny1, int ny2, int ndx1, int ndx2, int ndy1, int ndy2)
	{
		x1 = nx1;
		x2 = nx2;
		y1 = ny1;
		y2 = ny2;
		dx1 = ndx1;
		dx2 = ndx2;
		dy1 = ndy1;
		dy2 = ndy2;
		isHoriz = (dy1==dy2);
		clipped = false;
	}

	Edge nextEdge()
	{
		return *(new Edge(x1+dx1, x2+dx2, y1+dy1, y2+dy2, dx1, dx2, dy1, dy2));
	}

	void set(int nx1, int nx2, int ny1, int ny2, int d)
	{
		x1 = nx1;
		x2 = nx2;
		y1 = ny1;
		y2 = ny2;
		if (y1 == y2) {
			if (x1 < x2) {
				dx1 = -d;
				dx2 = dy1 = dy2 = d;
			}
			else {
				dx1 = d;
				dx2 = dy1 = dy2 = -d;
			}
		}
		else if (y1 < y2) {
			dy2 = d;
			dy1 = dx1 = dx2 = -d;
		}
		else {
			dy2 = -d;
			dy1 = dx1 = dx2 = d;
		}
		isHoriz = (dy1==dy2);
		clipped = false;
	}
};

class BPiece
{
public:
	Edge e[MAXEDGES];
	int numE;
};

class Border
{
public:
	BPiece piece[MAXEDGES/4];
	int nPieces;
	int perim;

	Border()
	{
		nPieces = perim = 0;
		for(int i=0; i<MAXEDGES/4; i++)
			piece[i].numE = 0;
	}
};

bool between(int a, int b, int c)
{
	if (a>=b && a <=c)
		return true;
	else
		return (a<=b && a>=c);
}

long calcPerim(Border *border)
{
	long perim=0;
	for(int i=0; i<border->nPieces; i++) {
		BPiece *bpiece = border->piece+i;
		for(int j=0; j<bpiece->numE; j++) {
			Edge *e = bpiece->e+j;
			perim += abs(e->x1-e->x2) + abs(e->y1-e->y2);
		}
	}
	return perim;
}

long calcArea(Border *border)
{
	long area=0;
	for(int i=0; i<border->nPieces; i++) {
		BPiece *bpiece = border->piece+i;
		for(int j=0; j<bpiece->numE; j++) {
			Edge *e = bpiece->e+j;
			area += (e->x2-e->x1)*(e->y1);
		}
	}
	return area;
}

bool clipHoriz(Edge& e, BPiece& elist, int d, int cx1, int cy1, int cx2, int cy2)
{
	int x1in = (e.x1 < cx1 ? -1 : e.x1 <= cx2 ? 0 : 1);
	int x2in = (e.x2 < cx1 ? -1 : e.x2 <= cx2 ? 0 : 1);
	bool y1in = (e.y1 > cy1 && e.y1 < cy2);
	bool y2in = (e.y2 > cy1 && e.y2 < cy2);
	if (x1in==0 && x2in==0 && y1in && y2in) {		// inside prev border
		e.clipped = true;
		return true;
	}
	else if (!y1in || !y2in) {				// no need to clip
		return false;
	}
	else if (x1in*x2in < 0) {				// break into two pieces
		if (e.x1 < e.x2) {
			elist.e[elist.numE++].set(cx2, e.x2, e.y1, e.y2, d);
			e.x2 = cx1;
		}
		else {
			elist.e[elist.numE++].set(cx1, e.x2, e.y1, e.y2, d);
			e.x2 = cx2;
		}
		return false;
	}
	else if (x1in == 0) {
		if (e.x1 < e.x2)
			e.x1 = cx2;
		else
			e.x1 = cx1;
	}
	else if (x2in == 0) {
		if (e.x2 < e.x1)
			e.x2 = cx2;
		else
			e.x2 = cx1;
	}
	return false;
}

bool clipVert(Edge& e, BPiece& elist, int d, int cx1, int cy1, int cx2, int cy2)
{
	bool x1in = (e.x1 > cx1 && e.x1 < cx2);
	bool x2in = (e.x2 > cx1 && e.x2 < cx2);
	int y1in = (e.y1 < cy1 ? -1 : e.y1 <= cy2 ? 0 : 1);
	int y2in = (e.y2 < cy1 ? -1 : e.y2 <= cy2 ? 0 : 1);
	if (x1in && x2in && y1in==0 && y2in==0) {		// inside prev border
		e.clipped = true;
		return true;
	}
	else if (!x1in || !x2in) {				// no need to clip
		return false;
	}
	else if (y1in*y2in<0) {				// break into two pieces
		if (e.y1 < e.y2) {
			elist.e[elist.numE++].set(e.x1, e.x2, cy2, e.y2, d);
			e.y2 = cy1;
		}
		else {
			elist.e[elist.numE++].set(e.x1, e.x2, cy1, e.y2, d);
			e.y2 = cy2;
		}
		return false;
	}
	else if (y1in==0) {
		if (e.y1 < e.y2)
			e.y1 = cy2;
		else
			e.y1 = cy1;
	}
	else if (y2in==0) {
		if (e.y2 < e.y1)
			e.y2 = cy2;
		else
			e.y2 = cy1;
	}
	return false;
}

BPiece clip(Edge e, int genPiece, int genEdge, Border* bdr, int d)
{
	BPiece ans;
	bool clipped = false;
	ans.e[0] = e;
	ans.numE = 1;
	for(int i=0; i<ans.numE; i++) {
		bool exit = false;
		for(int j=0; j<bdr->nPieces; j++) {
			for(int k=0; k<bdr->piece[j].numE; k++) {
				if (j == genPiece && k == genEdge)
					continue;
				Edge* bdre = bdr->piece[j].e+k;
				if (e.isHoriz) {	// horizontal edge
					if (bdre->isHoriz) {
						clipped = clipHoriz(ans.e[i], ans, d, min(bdre->x1, bdre->x2)-d, bdre->y1-d, max(bdre->x1, bdre->x2)+d, bdre->y1+d);
					}
					else {
						clipped = clipHoriz(ans.e[i], ans, d, bdre->x1-d, min(bdre->y1, bdre->y2)-d, bdre->x1+d, max(bdre->y1, bdre->y2)+d);
					}
				}
				else {
					if (bdre->isHoriz) {
						clipped = clipVert(ans.e[i], ans, d, min(bdre->x1, bdre->x2)-d, bdre->y1-d, max(bdre->x1, bdre->x2)+d, bdre->y1+d);
					}
					else {
						clipped = clipVert(ans.e[i], ans, d, bdre->x1-d, min(bdre->y1, bdre->y2)-d, bdre->x1+d, max(bdre->y1, bdre->y2)+d);
					}
				}
				if (clipped) {
					for(int ii=i+1; ii<ans.numE; ii++) {
						ans.e[ii-1] = ans.e[ii];
					}
					ans.numE--;
					i--;
					exit = true;
					break;
				}
			}
			if (exit)
				break;
		}
	}
	return ans;
}

bool add(Edge e, BPiece &piece)
{
	int i = piece.numE;
	if (i == 0) {
		piece.e[0] = e;
		piece.numE++;
		return true;
	}
	i--;
	if (e.isHoriz != piece.e[i].isHoriz) {
		if (e.x1 == piece.e[i].x2 && e.y1 == piece.e[i].y2) {
			piece.e[i+1] = e;
			piece.numE++;
			return true;
		}
	}
	else if (e.isHoriz && e.y1 == piece.e[i].y1) {
		if (between(e.x1, piece.e[i].x1, piece.e[i].x2)) {
			piece.e[i].x2 = e.x2;
			return true;
		}
	}
	else if (!e.isHoriz && e.x1 == piece.e[i].x1) {
		if (between(e.y1, piece.e[i].y1, piece.e[i].y2)) {
			piece.e[i].y2 = e.y2;
			return true;
		}
	}
	return false;
}

int main()
{
	int ncase, n, m, d;
	cin >> ncase;
	for(int icase=1; icase<=ncase; icase++) {
		cout << "Case " << icase << ":" << endl;
		cin >> n >> m >> d;
		Border* prevB = new Border;
		prevB->nPieces = 1;
		prevB->piece[0].numE = n;
		int x1, x2, y1, y2, sx1, sy1;
		cin >> x1 >> y1;
		sx1=x1;
		sy1=y1;
		for(int i=0; i<n-1; i++) {
			cin >> x2 >> y2;
			prevB->piece[0].e[i].set(x1, x2, y1, y2, d);
			x1 = x2;
			y1 = y2;
		}
		prevB->piece[0].e[n-1].set(x1, sx1, y1, sy1, d);

		areas[0] = calcArea(prevB);
		cout << "  Perimeters:";
		for(int iB = 1; iB<=m; iB++) {
			Border* currB = new Border;
			for(int i=0; i<prevB->nPieces; i++) {
				for(int j=0; j<prevB->piece[i].numE; j++) {
					BPiece elist = clip(prevB->piece[i].e[j].nextEdge(), i, j, prevB, d);
					for(int k=0; k<elist.numE; k++) {
						int l=0;
						while (l < currB->nPieces) {
							if (add(elist.e[k], currB->piece[l]))
								break;
							l++;
						}
						if (l == currB->nPieces) {
							add(elist.e[k], currB->piece[l]);
							currB->nPieces++;
						}
					}
				}
			}
			cout << " " << calcPerim(currB);
			areas[iB] = calcArea(currB);
			
			prevB = currB;
		}
		cout << "\n  Areas:";
		for(int iB = 1; iB<=m; iB++) {
			cout << " " << areas[iB]-areas[iB-1];
		}
		cout << endl;
		if (icase < ncase)
			cout << endl;

	}
	return 0;
}