Câu lạc bộ Robotics của trường đang luyện tập cho cuộc thi robot cứu hộ. Sa bàn thi đấu là một mê cung hình chữ nhật gồm ~n~ hàng và ~m~ cột ô vuông; các hàng được đánh số từ ~1~ đến ~n~ từ trên xuống dưới, các cột được đánh số từ ~1~ đến ~m~ từ trái sang phải. Ô ở hàng ~i~, cột ~j~ gọi là ô ~(i, j)~; mỗi ô là ô trống hoặc ô tường.

Robot xuất phát tại ô ~(1, 1)~ và cần đi tới ô ~(n, m)~; hai ô này luôn là ô trống. Mỗi bước, robot di chuyển sang một trong bốn ô kề cạnh với ô đang đứng (lên, xuống, sang trái, sang phải) và không được đi ra ngoài mê cung. Robot đi vào ô trống một cách tự do; muốn đi vào một ô tường, robot phải dùng mũi khoan phá ô tường đó (sau khi bị phá, ô trở thành ô trống). Phá tường rất tốn pin nên đội thi muốn phá càng ít ô tường càng tốt; số bước di chuyển thì không quan trọng.

Yêu cầu

Hãy tìm số ô tường ít nhất mà robot phải phá để đi được từ ô ~(1, 1)~ đến ô ~(n, m)~.

Dữ liệu vào

• Dòng thứ nhất chứa hai số nguyên ~n~ và ~m~;
• ~n~ dòng tiếp theo, dòng thứ ~i~ là một xâu gồm đúng ~m~ ký tự viết liền nhau mô tả hàng ~i~: ký tự . (dấu chấm) là ô trống, ký tự # là ô tường.

Kết quả ra

Ghi ra một số nguyên duy nhất là số ô tường ít nhất phải phá.

Ràng buộc

~1 \le n, m \le 1000~; ô ~(1, 1)~ và ô ~(n, m)~ là ô trống.

• Subtask 1 (15% số điểm – test 01–04): ~n \cdot m \le 16~;
• Subtask 2 (20% số điểm – test 05–08): ~n = 1~;
• Subtask 3 (20% số điểm – test 09–12): ~n, m \le 60~;
• Subtask 4 (45% số điểm – test 13–20): không có ràng buộc bổ sung.

Ví dụ

Dữ liệu vào mẫu 1

3 5
.####
##...
...#.

Kết quả ra mẫu 1

1

Giải thích

Robot phá ô tường ~(2,1)~ rồi đi ~(1,1) \to (2,1) \to (3,1) \to (3,2) \to (3,3) \to (2,3) \to (2,4) \to (2,5) \to (3,5)~: chỉ phá ~1~ ô tường. Không thể không phá ô nào vì cả hai ô kề với ô xuất phát đều là tường. Lưu ý đường đi trên có một bước đi lên (từ ô ~(3,3)~ lên ô ~(2,3)~); nếu chỉ đi xuống và sang phải thì robot phải phá ít nhất ~2~ ô tường.