#include <bits/stdc++.h> using namespace std; int a[114],b[114],n,m,sx,sy,sp,ans; bool mark[114]; int getdis(int czx, int lcx) { return (abs(a[czx]-a[lcx])+abs(b[czx]-b[lcx])); } void dfs(int step, int dis, int noww) { if(step == sp) { // cout << dis << endl; // cout << s << endl << endl; ans = min(ans,dis+getdis(noww,0)); return; } for(int i = 1; i <= sp; i++) { if(i==noww||mark[i])continue; mark[i]=true; dfs(step+1,dis+getdis(noww,i),i); mark[i]=false; } } void solve() { cin >> n >> m; cin >> sx >> sy; cin >> sp; a[0]=sx,b[0]=sy; for(int i = 1; i <= sp; i++) { cin >> a[i] >> b[i]; } ans = 0x3f3f3f3f; mark[0]=true; dfs(0,0,0); cout << "The shortest path has length "<<ans << endl; return; } signed main() { int T; cin >> T; while(T--)solve(); return 0; } /* 1 10 10 1 1 4 2 3 5 5 9 4 6 5 */