1720: 宝物与迷宫

小m最近在玩一个游戏，游戏充满了大量的迷宫，很多宝物包括通关用的重要道具都在迷宫里面。小m在迷宫里面只能朝上下左右移动，并且他靠着现代的科技，已经找到了迷宫的地图，但是迷宫里面还是有怪的，和怪物打起来会很浪费时间，所以他想走尽可能少的路的去找到宝物再原路返回。

由于迷宫确实太多了，如果那个迷宫不是必要道具所在的地方并且路程过远的话，他就直接不去了。

现在他把地图交给了你，请你跟他说一下他在迷宫中所走的路径总长是多少吧！

第一行一个T，代表一共有T个迷宫1 <= T  <= 100。

每个迷宫第一行输入一个n,m,k,R，代表迷宫的长度和宽度还有是否有必要去，k为1代表必须要去，0则代表非必要去，R代表预期的路径长度。(n,m,R <= 500)

接下来n行m列代表迷宫的布局。其中X代表墙壁，O代表可以用过，G代表宝物所在地，@代表出发点。

3 
3 3 1 3
X X G 
O O O
@ X X
4 4 0 3
X X G O
O X O O
@ X X O
O O O O
2 2 0 3
X G
@ O

12