1. 
package contestVolumes.volume104;

import java.util.*;

/**
 * FWP, Ausgewählte Probleme aus dem ACM Programming Contest, SS10 
 * Problem: 10496 - Collecting Beepers
 * Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=16&page=show_problem&problem=1437
 * 
 * @author Siegfried Ippisch
 * @version 1.0
 * 
 * Method : brute force
 * Status : Accepted
 * Runtime: 0.264
 */
public class CollectingBeepers {
	
	static class Point{
		private final int x;
		private final int y;
		
		public Point(int x, int y){
			this.x = x;
			this.y = y;
		}
		
		public int distance(Point other){
			return Math.abs(this.x - other.x) + Math.abs(this.y - other.y);
		}
		
		public String toString(){
			return "("+x+"|"+y+")";
		}
	}
	
	public static int minDistance(Point start, Point end, List<Point> list){
		if(list.isEmpty())
			return start.distance(end);
		
		int minDist = Integer.MAX_VALUE;
		for(Point p: list){
			List<Point> remaining = new LinkedList<Point>(list);
			remaining.remove(p);
			int dist = start.distance(p) + minDistance(p,end,remaining);
			minDist = Math.min(minDist, dist);
		}
		return minDist;
	}
	
	public static void main(String[] arsg){
		Scanner in = new Scanner(System.in);
		int cases = in.nextInt();
		
		while(cases-- > 0){
			in.nextInt();
			in.nextInt();
			
			Point start = new Point(in.nextInt(), in.nextInt());
			int c = in.nextInt();
			ArrayList<Point> beepers = new ArrayList<Point>(c);
			for(int i=0; i<c; i++)
				beepers.add(new Point(in.nextInt(), in.nextInt()));
			
			System.out.println("The shortest path has length "+ minDistance(start,start,beepers));
		}
		
		in.close();
	}
	
}