#include<bits/stdc++.h>
using namespace std;


int x[30],y[30],n,res;
bool vis[30];


void backtrack(int pos,int sum,int cnt)
{
	if(cnt==n)
	{
       sum+=((abs(x[pos]-x[0]))+(abs(y[pos]-y[0])));
     //  cout<<"sum "<<sum<<endl;
       res=min(res,sum);
       return;
	}
	else
	{
		for(int i=1;i<=n;i++)
		{
			if(vis[i]==false)
			{
				vis[i]=true;
				int ans=sum+((abs(x[pos]-x[i]))+(abs(y[pos]-y[i])));
			//	cout<<"i "<<i<<" "<<"ans "<<ans<<" cnt "<<cnt+1<<endl;
				backtrack(i,ans,cnt+1);
				vis[i]=false;
			}
		}
	}
}

int main()
{
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
    int t,i,j,k,row,clmn;
    memset(vis,false,sizeof(vis));
    cin>>t;
    while(t--)
    {
    	res=INT_MAX;
    	cin>>row>>clmn;
    	cin>>x[0]>>y[0];
    	cin>>n;
    	for(i=1;i<=n;i++)
    		cin>>x[i]>>y[i];
    	backtrack(0,0,0);
    	cout<<"The shortest path has length "<<res<<endl;
    }
    return 0;
}