Zjt and Sara will take part in a game, named Game III. Zjt and Sara will be in a maze, and Zjt must find Sara. There are some strang rules in this maze. If Zjt move a step, Sara will move a step in opposite direction.
Now give you the map , you shold find out the minimum steps, Zjt have to move. We say Zjt meet Sara, if they are in the same position or they are adjacent .
Zjt can only move to a empty position int four diraction (up, left, right, down). At the same time, Sara will move to a position in opposite direction, if there is empty. Otherwise , she will not move to any position.
The map is a N*M two-dimensional array. The position Zjt stays now is marked Z, and the position, where Sara stays, is marked E.
> . : empty position
> X: the wall
> Z: the position Zjt now stay
> S: the position Sara now stay
Your task is to find out the minimum steps they meet each other.
The input contains several test cases. Each test case starts with a line contains three number N ,M (2<= N <= 20, 2 <= M <= 20 ) indicate the size of the map. Then N lines follows, each line contains M character. A Z and a S will be in the map as the discription above.
For each test case, you should print the minimum steps. “Bad Luck!” will be print, if they can't meet each other.