Hidetaro, who loves fashion, has bought a new carpet. The carpet is a rectangle divided into a grid of H rows and W columns, and each cell is painted either white or black. The color of the cell in the i-th row from the top and the j-th column from the left (1 ≦ i ≦ H, 1 ≦ j ≦ W) is white if the j-th character of the string Si is ., and black if it is #.
Hidetaro came up with a game where he places a piece on the top-left cell of the carpet and performs the following operation several times to move the piece to the bottom-right cell.
Hidetaro wants to minimize the number of operations required to reach the destination. However, depending on the pattern of the carpet, it may be impossible to reach the destination.
Given the information about the pattern of the carpet, write a program that determines whether it is possible to move the piece from the top-left cell to the bottom-right cell by repeating the operation, and if possible, finds the minimum number of operations required.
. or # (1 ≦ i ≦ H).
The input is given from standard input in the following format.
H W
S1
S2
:
SH
If it is possible to move the piece from the top-left cell to the bottom-right cell by repeating the operation, output the minimum number of operations required. Otherwise, output -1. Output the result on a single line to standard output.
4 5 ...#. ##### ...#. #.###
9
For example, the operations shown in the figure are possible.
In the left example, it is possible to move the piece from the top-left cell to the bottom-right cell in 9 operations, and in the right example, it is possible in 13 operations.
It is impossible to reach the destination in fewer than 9 operations, so output 9.
3 3 ... ... ...
-1
It may be impossible to perform any operation from the start. In this case, it is impossible to move the piece to the bottom-right cell, so output -1.
1 5 .#.#.
4
5 5 ###.# .#... .#..# .#### ##..#
12
7 5 .#.## ##... .#.## .###. ##.#. ...#. ##.#.
12
Japan Information Olympiad Committee "21st Japan Information Olympiad JOI 2021/2022 Second Preliminary Round Problem"