#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; }