public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		String line = "";
		StringBuilder out = new StringBuilder();
		while ((line = in.readLine()) != null && line.length() != 0) {
			int test = Integer.parseInt(line.trim()), v[];
			for (int i = 0; i < test; i++) {
				in.readLine();
				start = toPoint(retInts(in.readLine()));
				int items = Integer.parseInt(in.readLine().trim());
				list = new Point[items + 1];
				list[0] = start;
				visited = new boolean[items + 1];
				for (int j = 1; j <= items; j++)
					list[j] = toPoint(retInts(in.readLine()));
				minPath = Integer.MAX_VALUE;
				back(0, 0, 0);
				out.append("The shortest path has length " + minPath + "\n");
			}
		}
		System.out.print(out);
	}