Pisces has a treasure map showing the location of the treasure. The treasure is in a cave which can be represented as a rectangular field of \(n*m\) cells, each cell is either empty or impassable. Empty cells are marked with '.' while impassable cells are marked with '#'. Pisces can move from one empty cell to an adjacent empty cell in one unit of time. Besides, there is a magic portal in the cave, and Pisces would be transferred from one side to the other immediately if he goes there. Pisces wants to know the minimum time that he can get the treasure.
Two cells are adjacent, means there is a common edge between these two cells.