Untitled

public class Solution {

	static Scanner sc;
	static int hx;
	static int hy;
	static PointCs[] p;
	static int[] v;
	static int min = 0;

	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("src/backtrack/hugogiaohang/input.txt"));
		sc = new Scanner(System.in);

		int T = sc.nextInt();

		for (int tc = 1; tc <= T; tc++) {
			min = 999999;

			int sx = sc.nextInt();
			int sy = sc.nextInt();
			hx = sc.nextInt();
			hy = sc.nextInt();

			int n = sc.nextInt();
			p = new PointCs[n];
			v = new int[n];
			for (int i = 0; i < n; i++) {
				int x = sc.nextInt();
				int y = sc.nextInt();
				p[i] = new PointCs(x, y);
			}

			backtrack(sx, sy, 0, 0);
			System.out.println("Case #" + tc + " " + min);
		}
	}

	private static void backtrack(int x, int y, int numberPizza, int cost) {
		// dieu kien dung
		if (min < cost) {
			return;
		}

		if (numberPizza == p.length - 1) {
			int fCost = Math.abs(x - hx) + Math.abs(y - hy);
			min = Math.min(min, cost + fCost);
		}

		for (int i = 0; i < p.length; i++) {
			if (v[i] == 0) {
				v[i] = 1;
				int xx = p[i].x;
				int yy = p[i].y;
				int currentCost = Math.abs(x - xx) + Math.abs(y - yy);
				backtrack(xx, yy, numberPizza + 1, cost + currentCost);
				v[i] = 0;
			}
		}

	}

	static class PointCs {
		int x, y;

		public PointCs(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}

}