Untitled

#include <bits/stdc++.h>
using namespace std;
void File() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}
const int inf=1e9;
void solve() {
    int x,y,st,ed,m;cin>>x>>y>>st>>ed>>m;
    vector<pair<int,int>>p;
    p.push_back({st,ed});
    for (int i = 0; i < m; ++i) {
        int a,b;cin>>a>>b;
        p.push_back({a,b});
    }
    vector<vector<int>>dis(p.size(),vector<int>(p.size(),inf));
    for (int i = 0; i < p.size(); ++i)
        for (int j = 0; j < p.size(); ++j)
            dis[i][j]=abs(p[i].first-p[j].first)+abs(p[i].second-p[j].second);
    for (int k = 0; k < p.size(); ++k)
        for (int i = 0; i < p.size(); ++i)
            for (int j = 0; j < p.size(); ++j)
                dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
    int n=p.size();
    int dp[n][1<<n];
    memset(dp,-1,sizeof dp);
    function<int(int,int)> tsp=[&](int i,int msk)->int{
        if(__builtin_popcount(msk)==p.size())
            return dis[i][0];
        int &ret=dp[i][msk];
        if(~ret)return ret;
        ret=inf;
        for (int j = 0; j < p.size(); ++j)
            if(!(msk&(1<<j)))
                ret=min(ret,tsp(j,msk|(1<<j))+dis[i][j]);
        return ret;
    };
    cout<<"The shortest path has length "<<tsp(0,1)<<'\n';
}
signed main() {
    File();
    int t;cin>>t;
    while(t--)
        solve();
}