题目描述

POJ 2907

生活在一个$\red{row×col}$的矩阵（均不超过$\red{20}$）的机器人每天要到$\red{n}$个目标点巡视，机器人起始位置坐标为$\red{（x，y）}$，机器人只能沿$\red{x，y}$轴移动，不能走对角线，问从起始位置出发，走过每个目标点之后返回到起始位置，最短的路径是多少？

输入格式

第一行为一个整数，表示测试数据的组数。

以后每组数据的第一行为两个整数，表示矩阵大小。

第二行为两个整数，即起始位置坐标。

第三行为一个整数即目标点数$\red{n（n≤10）}$，随后$\red{n}$行为各点坐标，均为整数。

输出格式

输出最短路径，每组测试数据一行。

样例

输入样例

1      
10 10  
1 1   
4　
2 3　　 
5 5
9 4
6 5

输出样例

The shortest path has length 24