1214_D. Treasure Island
All of us love treasures, right? That's why young Vasya is heading for a Treasure Island.

Treasure Island may be represented as a rectangular table n × m which is surrounded by the ocean. Let us number rows of the field with consecutive integers from 1 to n from top to bottom and columns with consecutive integers from 1 to m from left to right. Denote the cell in r-th row and c-th column as (r, c). Some of the island cells contain impassable forests, and some cells are free and passable. Treasure is hidden in cell (n, m).

Vasya got off the ship in cell (1, 1). Now he wants to reach the treasure. He is hurrying up, so he can move only from cell to the cell in next row (downwards) or next column (rightwards), i.e. from cell (x, y) he can move only to cells (x+1, y) and (x, y+1). Of course Vasya can't move through cells with impassable forests.

Evil Witch is aware of Vasya's journey and she is going to prevent him from reaching the treasure. Before Vasya's first move she is able to grow using her evil magic impassable forests in previously free cells. Witch is able to grow a forest in any number of any free cells except cells (1, 1) where Vasya got off his ship and (n, m) where the treasure is hidden.

Help Evil Witch by finding out the minimum number of cells she has to turn into impassable forests so that Vasya is no longer able to reach the treasure.

Input

First line of input contains two positive integers n, m (3 ≤ n ⋅ m ≤ 1 000 000), sizes of the island.

Following n lines contains strings s_i of length m describing the island, j-th character of string s_i equals "#" if cell (i, j) contains an impassable forest and "." if the cell is free and passable. Let us remind you that Vasya gets of his ship at the cell (1, 1), i.e. the first cell of the first row, and he wants to reach cell (n, m), i.e. the last cell of the last row.

It's guaranteed, that cells (1, 1) and (n, m) are empty.

Output

Print the only integer k, which is the minimum number of cells Evil Witch has to turn into impassable forest in order to prevent Vasya from reaching the treasure.

Examples

Input


2 2
..
..


Output


2


Input


4 4
....
#.#.
....
.#..


Output


1


Input


3 4
....
.##.
....


Output


2

Note

The following picture illustrates the island in the third example. Blue arrows show possible paths Vasya may use to go from (1, 1) to (n, m). Red illustrates one possible set of cells for the Witch to turn into impassable forest to make Vasya's trip from (1, 1) to (n, m) impossible.

<image>
```python
import sys
from io import BytesIO, IOBase
from collections import defaultdict, deque


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        import os
        self.os = os
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None
        self.BUFSIZE = 8192

    def read(self):
        while True:
            b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, self.BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, self.BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            self.os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")


def get_int():
    return int(input())


def get_ints():
    return list(map(int, input().split(' ')))


def get_int_grid(n):
    return [get_ints() for _ in range(n)]


def get_str():
    return input().strip()


def get_strs():
    return get_str().split(' ')


def flat_list(arr):
    return [item for subarr in arr for item in subarr]


def yes_no(b):
    if b:
        return "YES"
    else:
        return "NO"


def binary_search(good, left, right, delta=1, right_true=False):
    """
    Performs binary search
    ----------
    Parameters
    ----------
    :param good: Function used to perform the binary search
    :param left: Starting value of left limit
    :param right: Starting value of the right limit
    :param delta: Margin of error, defaults value of 1 for integer binary search
    :param right_true: Boolean, for whether the right limit is the true invariant
    :return: Returns the most extremal value interval [left, right] which is good function evaluates to True,
            alternatively returns False if no such value found
    """

    limits = [left, right]
    while limits[1] - limits[0] > delta:
        if delta == 1:
            mid = sum(limits) // 2
        else:
            mid = sum(limits) / 2
        if good(mid):
            limits[int(right_true)] = mid
        else:
            limits[int(~right_true)] = mid
    if good(limits[int(right_true)]):
        return limits[int(right_true)]
    else:
        return False


def prefix_sums(a):
    p = [0]
    for x in a:
        p.append(p[-1] + x)
    return p


def solve_a():
    n = get_int()
    d = get_int()
    e = get_int()
    best = float('inf')
    while n >= 0:
        best = min(best, n % d)
        n -= 5 * e
    return best


def solve_b():
    b = get_int()
    g = get_int()
    n = get_int()
    return min(b, n) - max(0, n - g) + 1


def solve_c():
    n = get_int()
    s = get_str()

    open = 0

    for idx, char in enumerate(s):
        if char == '(':
            open += 1
        else:
            open -= 1
        if open < - 1:
            return False
    return open == 0


def solve_d():
    n, m = get_ints()
    grid = [['#'] * (m + 2)]
    for row in range(n):
        grid.append(['#'] + list(get_str()) + ['#'])
    grid.append(['#'] * (m + 2))

    if n > 5 * 10 ** 5:
        for i in range(n):
            if grid[i + 1][1] == '#':
                return 0
        return 1

    if m > 5 * 10 ** 5:
        for j in range(m):
            if grid[1][j + 1] == '#':
                return 0
        return 1


    queue = deque([(1, 1)])
    vis_forward = [[0] * (m + 2) for _ in range(n + 2)]
    while queue:
        x, y = queue.popleft()
        if not vis_forward[x][y]:
            vis_forward[x][y] = 1
            if grid[x + 1][y] == '.':
                queue.append((x + 1, y))
            if grid[x][y + 1] == '.':
                queue.append((x, y + 1))

    back_queue = deque([(n, m)])
    vis_backward = [[0] * (m + 2) for _ in range(n + 2)]
    while back_queue:
        x, y = back_queue.popleft()
        if not vis_backward[x][y]:
            vis_backward[x][y] = 1
            if grid[x - 1][y] == '.':
                back_queue.append((x - 1, y))
            if grid[x][y - 1] == '.':
                back_queue.append((x, y - 1))

    score = [0] * (n + m - 1)

    if not vis_forward[n][m] or not vis_backward[1][1]:
        return 0

    for i in range(n):
        for j in range(m):
            score[i + j] += vis_forward[i + 1][j + 1] * vis_backward[i + 1][j + 1]

    if not max(score[0], score[-1]):
        return 0
    else:
        return min(2, min(score[1:-1]))


print(solve_d())
```