Bình đang tìm đường thoát khỏi một mê cung có dạng lưới kích thước \(R \times C\) ô vuông. Các hàng được đánh số từ \(1\) đến \(R\) từ trên xuống dưới, các cột được đánh số từ \(1\) đến \(C\) từ trái qua phải. Ô ở hàng \(i\), cột \(j\) được ký hiệu là \((i, j)\).

Tại mỗi bước, từ ô hiện tại, Bình có thể di chuyển sang một trong bốn ô kề cạnh (chung cạnh). Mê cung gồm hai loại ô:

• Ô trống (ký hiệu là \(.\)): Bình có thể đi vào miễn phí (chi phí bằng \(0\)).
• Ô vật cản (ký hiệu là \(#\)): Bình cần phá hủy vật cản này để đi qua (chi phí bằng \(1\)).

Hãy tìm số lượng vật cản ít nhất cần phá hủy để Bình đi từ ô xuất phát \((1, 1)\) đến ô đích \((R, C)\).

Định dạng đầu vào

• Dòng đầu chứa hai số nguyên \(R\) và \(C\) (\(1 \le R, C \le 1000\)).
• \(R\) dòng tiếp theo, mỗi dòng chứa một chuỗi ký tự độ dài \(C\) mô tả mê cung (chỉ gồm các ký tự \(.\) và \(#\)). Ô \((1, 1)\) và ô \((R, C)\) luôn là \(.\).

Định dạng đầu ra

• Một số nguyên duy nhất là số lượng vật cản tối thiểu cần phá hủy.

Ràng buộc

Ví dụ

Input:

3 3
.##
.#.
..#

Output:

1