文理学院程序设计在线练习


魔法棋盘

Time Limit: 3 Second(s)    Memory Limit: 32 MB

Total Submission(s): 11   Accepted Submission(s): 5
Problem Description

大雄这次不小心掉到了一个巨大的棋盘上,听说这个魔法棋盘会使人变得勤劳哦。大雄转了半天,还是没找到出去的方法……不过大雄发现在棋盘的左上角,有10个魔法阵,而在整个棋盘上一共散落着恰好10个棋子(如下图所示):


于是出去的方法是显而易见的了,大雄不得不把所有的棋子推到这些魔法阵中。然而这些棋子太大了,大雄一次只能将一个棋子推到其周围的某个格子上(上下左右以及对角)(如上图所示),仅当目标格子里已有棋子时则无法推动,每推动一次记为一步。请问大雄最少需要用几步才能使所有棋子归位?
为方便表示设棋盘最左上角的格子坐标为(1,1),图中棋子的坐标为(6,3)。

Input

第一行包含一个整数T,表示数据组数。(T<=10)
接下来T组数据,每组数据包含恰好10行,每行格式为”(x,y)”,其中x,y为正整数,表示棋子坐标,数据保证10个棋子坐标互不相同,1<= x,y <=100000。

Output

对于每组数据,输出一行,仅包含一个非负整数,表示大雄达成目标所需要的最少步数。

Sample Input
1
(1,1)
(1,2)
(1,3)
(1,4)
(2,1)
(2,2)
(2,3)
(4,3)
(3,2)
(4,1)
Sample Output
2
Source

第12届校赛