说明

在实际工程中，铺设电缆等设施时，既考虑障碍物的问题，又要考虑造价最低。随着电子设备的普及，工程中需要大量的电路板。每个电路板上有很多线路，我们在设计电路时，尽可能地节约成本，如果一个电路板省下一分钱，也将是一笔很大的财富。布线问题就是在m×n的方格阵列中，指定一个方格的中点a，另一个方格的中点b，问题要求找出a到b的最短布线方案。布线时只能沿直线或直角，不能走斜线。为了避免线路相交，已布过线的方格做了封锁标记（灰色），其他线路不允许穿过被封锁的方格。

输入格式

第一行是一个整型数C(C<100)表示共有C组测试数据。

每组测试数据第一行输入方格阵列m,n（1<=m,n<=50）。

接下来输入障碍物坐标行列x,y，输入0 0结束（1<=x,y <=50）。

最后两行，输入起点坐标a.x,a.y（1<=a.x,a.y <=50）， 输入终点坐标b.x,b.y（1<=b.x,b.y <=50）。

输出格式

对于每一组输入，输出满足条件的最短距离。

每组的输出占一行。

样例

2
5 6
1 6
2 3
3 4
3 5
5 1
0 0
2 1
4 6
6 7
1 5
2 3
3 3
3 5
3 6
4 3
5 6
6 4
6 5
6 6
0 0
3 1
6 7

7
11

来源

《趣学算法》6.4节