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 \leq N \leq 1\,000)~ and ~M~ ~(1 \leq M \leq 1\,000)~, 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