#include<bits/stdc++.h> #define int long long using namespace std; namespace Fast{ inline long long fr(){ register long long x = 0,f = 1; static char c = getchar(); while (c < '0' || c > '9'){ if (c == '-'){ f = -1; } c = getchar(); } while (c >= '0' && c <= '9'){ x = (x << 1) + (x << 3) + (c ^ 48); c = getchar(); } return x * f; } inline void fw(long long x){ if (x == 0){ putchar('0'); return ; } if (x < 0){ x = -x; putchar('-'); } stack <char> s; while (x){ s.push((x % 10) + '0'); x /= 10; } while (!s.empty()){ putchar(s.top()); s.pop(); } } inline void CCF(int opt){ ios::sync_with_stdio(false); if (opt == 0){ cout.tie(0); return ; } if (opt >= 1){ cin.tie(0); } if (opt >= 2){ cout.tie(0); } } inline void DEBUG(){ puts("IAKIOI"); } } using namespace Fast; int a,b,x,y,n,xx[15],yy[15],res[15],ans = 2147483647; bool f[15]; void dfs(int cur,int lstx,int lsty,int len){ if (cur > n){ int sum = len + abs(lstx - x) + abs(lsty - y); ans = min(ans,sum); return ; } for (int i = 1;i <= n;i++){ if (f[i]){ continue; } f[i] = true; res[cur] = i; dfs(cur + 1,xx[i],yy[i],len + abs(lstx - xx[i]) + abs(lsty - yy[i])); f[i] = false; } } void slove(){ ans = 2147483647; a = fr(),b = fr(),x = fr(),y = fr(),n = fr(); for (int i = 1;i <= n;i++){ xx[i] = fr(),yy[i] = fr(); } dfs(1,x,y,0); cout<<"The shortest path has length "<<ans<<'\n'; return ; } signed main(){ int t = fr(); while (t--){ slove(); } return 0; }