L. Bee coloring book
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Veronica is very good at drawing and coloring pictures. Igor and Ira bought her a new bee coloring book.

The coloring consists of $$$n$$$ lines, each contains exactly $$$m$$$ cells. Each cell is a regular hexagon, like a honeycomb in bees, and has no more than 6 neighbors. As an example, the $$$5 \times 5$$$ field looks like this:

Initially, some cells in the coloring are already colored. Veronica wants to get a continuous line of colored cells that connects the first row with the $$$n$$$-th row by coloring the minimum number of cells.

Input

The first line contains two integers $$$n$$$, $$$m$$$ $$$(1 \leq n, m \leq 1000)$$$  — the number of lines in the coloring and the number of cells in each line.

Next, $$$n$$$ lines are given, each line contains exactly $$$m$$$ characters and each line consists only of the characters «.» and «#». The symbol «.» means that the cell is not colored, «#»  — the cell is colored.

Output

Print one integer – the minimum number of cells that need to be colored to connect the first row with the $$$n$$$-th row.

Example
Input
5 5
....#
.#...
.#...
...#.
.#...
Output
2