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.

Ví dụ

Input:

3 3
.##
.#.
..#

Output:

1

Ràng buộc