Untitled

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

class Point {
	int x;
	int y;

	Point(int _x, int _y) {
		this.x = _x;
		this.y = _y;

	}
	// public static int compare() {
	//
	// }

}

public class HugoGiaoHang {
	static int N, Sx, Sy, Hx, Hy;
	static Point[] point;
	static int cbiDuLieu[][], ans, visitToaDo[];

	public static void main(String[] args) {
		try {
			System.setIn(new FileInputStream("hugoGiaoHang"));
		} catch (FileNotFoundException e) {
			e.printStackTrace();
		}
		Scanner sc = new Scanner(System.in);
		int numTest = sc.nextInt();
		for (int tc = 1; tc <= numTest; tc++) {
			Sx = sc.nextInt();
			Sy = sc.nextInt();
			Hx = sc.nextInt();
			Hy = sc.nextInt();
			N = sc.nextInt();
			point = new Point[N + 2];
			point[0] = new Point(Sx, Sy);
			point[N + 1] = new Point(Hx, Hy);

			for (int i = 1; i <= N; i++) {
				point[i] = new Point(sc.nextInt(), sc.nextInt());
			}
			cbiDuLieu = new int[N + 2][N + 2];
			DuLieu();
			// for (int i = 0; i <= N + 1; i++) {
			// for (int j = 0; j <= N + 1; j++) {
			// System.out.print(cbiDuLieu[i][j] + " ");
			// }
			// System.out.println();
			// }
			visitToaDo = new int[N + 2];
			ans = Integer.MAX_VALUE;
			backTrack(0, 0, 0);
			System.out.println("Case #" + tc + " " + ans);
		}
	}

	public static void DuLieu() {
		for (int i = 0; i < N + 1; i++) {
			for (int j = i + 1; j <= N + 1; j++) {

				int u = Math.abs(point[i].x - point[j].x);
				int v = Math.abs(point[i].y - point[j].y);
				cbiDuLieu[i][j] = u + v;
				cbiDuLieu[j][i] = u + v;
			}
		}
	}

	public static void backTrack(int numViTriGiaoHang, int Start, int quangDuong) {
		if (numViTriGiaoHang == N) {
//			for (int i = 0; i <= N + 1; i++) {
//				System.out.print(visitToaDo[i] + " ");
//			}
//			System.out.println();
//			System.out.println();
			ans = Math.min(ans, quangDuong + cbiDuLieu[Start][N + 1]);//BT N vtri giao hang + quang duong ve nha
			return;
		}
//		 if (quangDuong + cbiDuLieu[numViTriGiaoHang][N + 1] > ans) {
//		 ans = Math.min(ans, quangDuong + cbiDuLieu[numViTriGiaoHang][N + 1]);
//		 return;
//		 }
		
		for (int i = 1; i <= N; i++) {
			if (visitToaDo[i] == 0) {
				visitToaDo[i] = 1;

				backTrack(numViTriGiaoHang + 1, i, quangDuong + cbiDuLieu[Start][i]);
				visitToaDo[i] = 0;
			}
		}

	}

}