After dealing with his $N$ by $M$ grid for too long, Santa asks you to find the minimum number of cookies he must eat to travel from $(1,1)$ to $(N,M)$.

He can also only travel to cells that share a side with his current cell (i.e., not diagonally).

Each cell can either be an open space, denoted by ., or a cookie, denoted by C.

Whenever he enters a cell with a cookie, he always eats it.

Since Santa wants to maintain his slim figure, help him find the minimum number of cookies he needs to eat to travel from the top-left corner to the bottom-right corner!

Input Specification

The first line will contain $N$ $(1\le N\le 1000)$ and $M$ $(1\le M\le 1000)$, the number of rows and the numbers of columns in his grid.

The next $N$ lines will each contain $M$ cells.

Output Specification

Output the minimum amount of cookies that must be collected to travel from $(1,1)$ to $(N,M)$.

Sample Input 1

6 4
C..C
.CCC
CC.C
..CC
CC..
C.C.

Sample Output 1

3

Sample Input 2

5 5
.....
..CC.
.....
.....
.....

Sample Output 2

0