import java.io.IOException; import java.util.Scanner; public class Main { static int n, r, c; static int[][] dp, beepers; static int max = 1 << 23; static int dist(int a, int b){ return Math.abs(beepers[a][0] - beepers[b][0]) + Math.abs(beepers[a][1] - beepers[b][1]); } static int solve(int i,int bitmask) { if((bitmask == (1 << (n + 1)) - 1)){ return dist(0, i); }else if(dp[i][bitmask] != -1){ return dp[i][bitmask]; }else{ dp[i][bitmask] = max; for (int j = 0; j <= n; j++) { if(((1<<j) & bitmask) == 0) dp[i][bitmask] = Math.min(dp[i][bitmask], dist(i, j) + solve(j, bitmask | (1<<j))); } return dp[i][bitmask]; } } public static void main(String[] args) throws NumberFormatException, IOException { Scanner sc = new Scanner(System.in); StringBuilder out = new StringBuilder(); int t = sc.nextInt(); int si,sj; for (int i = 0; i < t; i++) { r = sc.nextInt(); c = sc.nextInt(); si = sc.nextInt(); sj = sc.nextInt(); n = sc.nextInt(); beepers = new int[n+1][2]; dp = new int[n+1][(1<<(n + 1)) +1 ]; for (int j = 0; j < dp.length; j++) { for (int k = 0; k < dp[0].length; k++) { dp[j][k] = -1; } } beepers[0][0] = si; beepers[0][1] = sj; for (int j = 1; j <= n; j++) { beepers[j][0] = sc.nextInt(); beepers[j][1] = sc.nextInt(); } out.append("The shortest path has length " + solve(0,1) + "\n"); } System.out.print(out); } }