1699 - pyy's road

Time Limit : 1 Second

Memory Limit : 128 MB

Submission: 35

Solved: 9

Description

有一天,路痴pyy来到了主校区。然后迷路了。。。


他知道主校区的路都是横平竖直的,所以他只能往上下左右四个方向走。


他还有一张奇怪的地图(要是不奇怪就不会迷路了)。


地图有N行M列,每一个位置是 @ 或者 # 。


@表示这里可以通过,#表示这里不能通过。


这张地图标记出当前的位置,和终点的位置。


pyy现在想知道从当前位置到终点 最短 还有多远。


如果pyy不能走到终点,会大骂一句“垃圾道路”。


 


注意:众所周知,学校周围是有栏杆的。作为好学生的pyy不会翻越这些栏杆,去抄近路。


换而言之,pyy不会走出地图。


 

Input

第一行为数据组数T


每组数据的第一行为N, M。代表地图有N行M列。


第二行为Xs,Yx,Xt,Yt。表示当前的坐标和终点的坐标(从1开始)。


接下来的N行,每行M个字符。输入保证这些字符只可能为@或者#。


1 <= T <= 10


1 <= N, M <= 1000, 1 <= Xs, Xt <= N, 1 <= Yx, Yt <= M。


 

Output

对于每组数据输出一行。


如果可以走到,输出"Case #ti: d"(去掉引号)。ti为第几组数据,d为最短的距离。


如果不能走到,输出"Case #ti: lj road"(去掉引号)。ti同上。


 

sample input
2
2 2
1 1 2 2
@@
@@
2 2
1 1 2 2
@#
#@
sample output
Case #1: 2
Case #2: lj road
hint
source
pyy
© 2015 HUST ACMICPC TEAM. All Right Reserved.