Untitled

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;

int dist[12][12];
int visited[12];
int Map[12][2];
int nTestcase, N, xStart, yStart, xEnd, yEnd, step, Min;

void BFS(int start) {
	for (int i = 0; i < N + 2; i++) {
		int x = Map[start][0] > Map[i][0] ? Map[start][0] - Map[i][0] : Map[i][0] - Map[start][0];
		int y = Map[start][1] > Map[i][1] ? Map[start][1] - Map[i][1] : Map[i][1] - Map[start][1];
		dist[start][i] = x + y;
	}
}

void backtrack(int Start, int nPizza) {
	if (step >= Min) {
		return;
	}
	if (nPizza == N) {
		step += dist[Start][N + 1];
		Min = Min > step ? step : Min;
		step -= dist[Start][N + 1];
		return;
	}
	for (int i = 1; i < N + 1; i++) {
		if (visited[i] == 0) {
			visited[i] = 1;
			step += dist[Start][i];
			backtrack(i, nPizza + 1);
			visited[i] = 0;
			step -= dist[Start][i];
		}
	}
}


int main() {
	//freopen("input.txt", "r", stdin);
	cin >> nTestcase;
	for (int testcase = 1; testcase <= nTestcase; testcase++) {
		cin >> xStart >> yStart >> xEnd >> yEnd >> N;
		Map[0][0] = xStart;
		Map[0][1] = yStart;
		Map[N+1][0] = xEnd;
		Map[N+1][1] = yEnd;
		for (int i = 1; i <= N; i++) {
			cin >> Map[i][0] >> Map[i][1];
		}
		for (int i = 0; i < N + 2; i++) {
			BFS(i);
			visited[i] = 0;
		}
		step = 0;
		Min = 1000000000;
		visited[0] = 1;
		backtrack(0, 0);
		cout << "Case #" << testcase << " " << Min << endl;
	}
	return 0;
}