An đang lái xe trên một bãi thử nghiệm hình lưới ô vuông kích thước \(R \times C\). Lưới gồm các ô trống \(.\) và các chướng ngại vật \(#\). An xuất phát từ ô \((1, 1)\) và cần lái xe đến ô \((R, C)\).

Khi lái xe, hướng di chuyển ban đầu của xe có thể chọn là một trong bốn hướng: Lên, Xuống, Trái, Phải. Khi di chuyển:

• Nếu xe đi thẳng tiếp tục theo hướng cũ sang ô kề cạnh kề bên, chi phí rẽ hướng bằng \(0\).
• Nếu xe rẽ hướng (chuyển sang hướng vuông góc với hướng vừa đi), chi phí rẽ hướng bằng \(1\).

Chú ý: Xe chỉ được di chuyển vào các ô trống \(.\) và không được đi ra ngoài lưới.

Hãy giúp An tìm số lần rẽ hướng ít nhất để đi tới đích.

Đị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ả lưới. Ô \((1, 1)\) và ô \((R, C)\) luôn là \(.\).

Định dạng đầu ra

• Một số nguyên duy nhất là số lần rẽ hướng tối thiểu. Nếu không thể đi tới, in ra \(-1\).

Ràng buộc

Ví dụ

Input:

3 3
...
.#.
...

Output:

1