#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){ 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>>sx>>sy>>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; }