Background

As everyone knows, Wzf always wants to do homework.

But today, WSD snatched its homework!!!

Wzf is furious!!!

It decides to rush toward the homework at top speed.

In front of it is a maze, and the homework is inside!

Problem Description

There is a maze with $n$ rows and $m$ columns:

Wzf starts from the top-left corner of the maze (row $1$, column $1$). Each second, it can:

1. Choose a direction (up / down / left / right).
2. Choose a non-negative integer $m$.
3. Take one step in the chosen direction, moving $2^m$ cells:
   • It must not cross any obstacle along the way.
   • The landing cell must not contain an obstacle.
   • It cannot go outside the maze.

Find the minimum number of seconds Wzf needs to reach the goal.

Input Format

The first line contains two integers $n, m$ with $1 \le n, m \le 1000$.

The next $n$ lines each contain $m$ characters.

It is guaranteed that there is exactly one #.

It is guaranteed that the cell at row $\bm 1$, column $\bm 1$ is not X.

Output Format

Output a single integer, the minimum number of seconds Wzf needs to reach the goal.

If Wzf cannot reach the goal, output $-1$.

2 2
$$
.#

2

Hint

Translated by ChatGPT 5