Courtyard X26694

To attend her next class, Alice has to cross the UPF courtyard. However, there are a number of obstacles in her way, both objects (tables, chairs, benches) and people (students standing or sitting). Alice wants to compute the shortest path to the other side of the courtyard.

To compute the shortest path, Alice approximates the courtyard as a matrix of cells of a given dimension, such that each cell is either free or occupied. Alice can only move horizontally or vertically between cells, and she can only go to a cell that is free. Help Alice find the shortest path.

Input

The input consists of several test cases. Each test case starts with two numbers H≤ 500 and W≤ 500 describing the height and width of the courtyard. The next H lines describes the courtyard itself, with dots marking free cells and X’s marking occupied cells.

Output

For each test case, output the length of the shortest path from the cell (1,1) to the cell (H,W), or −1 if there exists no path.