Problem Description
If you ask one student of HDU “who is the superstar in HDU now?” ,the answer must be “HDU CakeMan” .He sells little cakes in the gate of the HDU students’ dormitory every day .As he says “做人要有小蛋糕精神,不怕风吹雨打,永远三块钱”.But he has no permission. So once seeing ChengGuan coming , he have to run home as fast as possible.
Now , ChengGuan is coming now. After some days investigation,ChengGuan have the map of HDU , and know the home of CakeMan, so can you tell me the minimum time ChengGuan cost to catch CakeMan?
Once seeing ChengGuan coming, CakeMan will run home through a way which cost the least time , if there are more than one ways , he will randomly choose one ,so none knows which way he takes this time.
ChengGuan are be ordered to catch him today, so they want to know the nearest grid which CakeMan will surely pass (excluding the start point of CakeMan and CakeMan’s home).
Input
The first line of input gives the number of cases, T (at most 90).
the first line of each case has four numbers n,m. (2<=n,m<=100)
then n lines with m characters describe the maze
‘D’ represents the init position of CakeMan.
‘S’ represents the position of the home of CakeMan.
‘C’ represents the position of the home of ChengGuan.
‘.’ represents the grids can be walked on.
‘X’ represents the wall which can not be stepped on.
‘A’ A is a integer between 0 and 9, represents the grid stands one HDU student who want A pack of Cake. when CakeMan pass on the grid has a integer on it ,he have to stay A seconds to sell cakes to the students (total costs A + 1 seconds to pass the grid), otherwise he pass the grid in one second. And the data makes sure that there must be at least one way to let CakeMan home.
Output
If there is one nearest grid on the map where ChengGuan can catch CakeMan surely, output how much time(one second one step) can ChengGuan get to this grid.output -1 other wise.
Sample Input
1
4 9
..X..S...
.........
X...123..
D.......C
Sample Output
7
