Navigate X31624

In some stages of the video game, the player has to navigate the ship through a maze. At each moment, the player can move the ship left or right, or remain in the same place. The ship then moves one step forward, and the process is repeated. The stage succeeds if the ship reaches the top row of the maze without colliding with an obstacle.

Input

The input consists of several test cases. Each test case consists of two integers 1≤ H,W ≤ 1000 representing the height and width of the maze. The following H lines contain W characters each, representing the maze itself. An ’X’ marks an obstacle, and an ’S’ marks the starting point of the ship.

Output

For each test case, a number on a single line representing the minimum number of movements (left or right) required to successfully navigate the maze. If it is not possible to reach the top of the maze, output −1.