题目描述

薯条哥有一个$n$行$m$列的棋盘，并且有一个棋子初始位于$(1,1)$。

棋盘由字符. ,*组成，.代表该位置可行走，*代表该位置不能行走。

薯条哥每次可以让棋子往右，往下或者往右下移动若干个位置，他想知道，移动到右下角$(n,m)$一共需要多少步？

输入描述

第一行，两个正整数$n$和$m(1\le n,m\le 2000)$。

接下来的$n$行，每行$m$个字符，用来表示棋盘

输出描述

一个整数，表示所需要的最少步数。如果无法到达右下角，输出-1。

样例

输入

4 3
...
.*.
...
**.

输出

2