抢机器

Description:

程序设计实践周开始啦！南邮的同学们都非常激动，因为他们准备冲向机房抢占机器。我们可以把机房和同学看作一个n行m列的矩阵A，Aij=1表示第i行第j列是一个机房，Aij=0表示该位置是一个准备抢机器的同学。当然，一个机房里面有很多机器，多个同学可以到同一个机房抢占机器。如果一个同学在x1行y1列，他准备到x2行y2列的机房抢机器，那么他将花费|x1-x2|+|y1-y2|的时间。每个同学都希望花费最少的时间，因为这样他们可以抢占更好的机器。求出所有同学抢机器花费最少的总时间。

Input:

第一行是一个整数T(1<=T<=10)，表示共有T组数据。

对于每组数据：

第一行有两个整数N，M（1<=N,M<=1000）。

接下来共N行，每行M个整数，Aij，0<=Aij<=1。

每组数据保证至少有一个机房。

Output:

每行输出一个整数，表示所有同学抢占机器花费最少的总时间。

Sample Input:

3
2 2
0 1
0 0
2 2
0 0
1 1
3 4
1 1 1 0
1 1 0 0
0 0 0 0

Sample Output:

4
2
11

Note:

 

本题由旧版NOJ导入，来源：ym