Problem Description

Now SuSu and his companions arrived at Xiangling's hometown - ZiRong Forest. To drive SuSu out of these area, "Piaorou Bro" Lingduan set the forest on fire. To prevent the trees from burning down, SuSu must find the exit of the forest as quickly as possible and kill Lingduan. If he could not kill Lingduan in TIME seconds, the forest will suffer too much damage to be recovered. What was worse, there are some horrible monsters in the forest. SuSu would suffer a certain damage when he kill a monster on his way to the exit. For the purpose of save energy and to kill Lingduan more easily, the damage SuSu suffer from the monsters should be the fewer the better. Please help SuSu to find a reasonable path which can lead him to the exit in TIME seconds, and suffers the minimum damage at the same time.

To represents the ZiRong forest, we use a n * m maze:
'S' and 'L' represents the position of SuSu and Lingduan at the very beginning. Each of them appears in the maze once and only once.
'F' represents fire where SuSu can not step into.
A number (from 0 to 9) indicates there is one monster in this grid ,and it's attack is the corresponding number.

Every second SuSu can choose a direction and go forward 1 ~ K steps, and for all monsters' attack in the grids he passed by(if the grid do exist a monster), we accumulate them and get a sum. The damage SuSu will suffer is the square of this sum.

Input

The first line of input should give the number of cases, T(1<=T<=50).
The first line of each case are four numbers N, M, TIME, K. (2 <= N, M <= 100, 1 <= TIME, K <= 100)
Followed by N lines each with M characters, described the ZiRong forest.

Output

If SuSu can reach the position "Piaorou Bro" stands in time, output the minimum damage.
Otherwise output "胜败兵家事不期 卷土重来是大侠".
Following the case number (start with 1).

5
3 3 2 2
S19
111
F1L
3 3 3 2
S19
111
F1L
5 4 5 1
S111
9FF1
9FF1
9111
FFLF
5 4 4 100
S111
9FF1
9FF1
9111
FFLF
5 4 100 1
S111
9FF1
9FF1
9111
FFLF

Case 1: 101
Case 2: 5
Case 3: 胜败兵家事不期 卷土重来是大侠
Case 4: 19
Case 5: 7

Author

NotOnlySuccess