import java.util.*;

public class Borders {

public static final int MAXEDGES = 200;
public static final int MAXBORDERS = 20;

public static final long[] perims = new long[MAXBORDERS+1];
public static final long[] areas = new long[MAXBORDERS+1];

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

public static 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 += Math.abs(e.x1-e.x2) + Math.abs(e.y1-e.y2);
		}
	}
	return perim;
}

public static 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;
}

public static boolean 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);
	boolean y1in = (e.y1 > cy1 && e.y1 < cy2);
	boolean 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;
}

public static boolean clipVert(Edge e, BPiece elist, int d, int cx1, int cy1, int cx2, int cy2)
{
	boolean x1in = (e.x1 > cx1 && e.x1 < cx2);
	boolean 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;
}

public static BPiece clip(Edge e, int genPiece, int genEdge, Border bdr, int d)
{
	BPiece ans = new BPiece();
	boolean clipped = false;
	ans.e[0] = e;
	ans.numE = 1;
	for(int i=0; i<ans.numE; i++) {
		boolean 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, Math.min(bdre.x1, bdre.x2)-d, bdre.y1-d, Math.max(bdre.x1, bdre.x2)+d, bdre.y1+d);
					}
					else {
						clipped = clipHoriz(ans.e[i], ans, d, bdre.x1-d, Math.min(bdre.y1, bdre.y2)-d, bdre.x1+d, Math.max(bdre.y1, bdre.y2)+d);
					}
				}
				else {
					if (bdre.isHoriz) {
						clipped = clipVert(ans.e[i], ans, d, Math.min(bdre.x1, bdre.x2)-d, bdre.y1-d, Math.max(bdre.x1, bdre.x2)+d, bdre.y1+d);
					}
					else {
						clipped = clipVert(ans.e[i], ans, d, bdre.x1-d, Math.min(bdre.y1, bdre.y2)-d, bdre.x1+d, Math.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;
}

public static boolean 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;
}

public static void  main(String [] args)
{
	Scanner in = new Scanner(System.in);
	int ncase, n, m, d;
	ncase = in.nextInt();
	for(int icase=1; icase<=ncase; icase++) {
		System.out.println("Case " + icase + ":");
		n = in.nextInt();
		m = in.nextInt();
		d = in.nextInt();
		Border prevB = new Border();
		prevB.nPieces = 1;
		prevB.piece[0].numE = n;
		int x1, x2, y1, y2, sx1, sy1;
		x1 = in.nextInt();
		y1 = in.nextInt();
		sx1=x1;
		sy1=y1;
		for(int i=0; i<n-1; i++) {
			x2 = in.nextInt();
			y2 = in.nextInt();
			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);
		System.out.print("  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++;
						}
					}
				}
			}
			System.out.print(" " + calcPerim(currB));
			areas[iB] = calcArea(currB);

			prevB = currB;
		}
		System.out.print("\n  Areas:");
		for(int iB = 1; iB<=m; iB++) {
			System.out.print(" " + (areas[iB]-areas[iB-1]));
		}
		System.out.println();
		if (icase < ncase)
			System.out.println();

	}
}
}

class Edge
{
	public int x1, y1, x2, y2;
	public int dx1, dx2, dy1, dy2;
	boolean isHoriz;
	boolean clipped;

	public Edge()
	{}

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

	public 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;
	}

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

	public 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 = new Edge[Borders.MAXEDGES];
	public int numE;

	public BPiece()
	{
		for(int i=0; i<Borders.MAXEDGES; i++)
			e[i] = new Edge();
	}
}

class Border
{
	public BPiece[] piece = new BPiece[Borders.MAXEDGES/4];
	public int nPieces;
	public int perim;

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