Trong một trò chơi tìm kho báu, bản đồ được mã hóa thành một bảng hình chữ nhật có ~M~ hàng và ~N~ cột. Các hàng được đánh số từ ~1~ đến ~M~, các cột được đánh số từ ~1~ đến ~N~, ô ở hàng ~i~, cột ~j~ trên bảng gọi là ô ~(i, j)~ có giá trị là một trong bốn loại ký tự:

• '0': mô tả ô đất liền;

• '1': mô tả ô biển;

• '@': mô tả ô vị trí xuất phát của nhân vật (luôn ở trên đất liền);

• '#': mô tả ô chứa kho báu (luôn ở trên đất liền).

Nhân vật không biết bơi nên sẽ không thể đi vào ô biển và luôn luôn đứng ở ô đất liền. Nhân vật có thể di chuyển trên bản đồ theo các cách sau:

• Đi bộ tự do sang các ô đất liền chung cạnh.

• Nhảy qua biển theo một trong ~4~ hướng Đông, Tây, Nam, Bắc đến ô đất liền đầu tiên trên hướng nhảy đó.

Yêu cầu: Nhân vật xuất phát ở ô có ký tự '@', và muốn di chuyển đến ô có ký tự '#' chứa kho báu. Vì mỗi lần nhảy qua biển tiêu hao nhiều năng lượng, hãy giúp nhân vật tìm số lần nhảy nhỏ nhất để có thể di chuyển đến ô có kho báu.

Input

• Dòng đầu tiên gồm hai số nguyên ~M, N~ ~(1 \le M, N \le 10^3)~;

• ~M~ dòng tiếp theo, mỗi dòng gồm ~N~ ký tự mô tả bản đồ.

Output

Một số nguyên duy nhất là kết quả của bài toán.

Scoring

Sample Input 1

4 8
@0011011
11111011
1001101#
11111011

Sample Output 1

2

Sample Input 2

1 9
@1011101#

Sample Output 2

3

Notes

• Ví dụ 1: Một cách di chuyển có số lần nhảy nhỏ nhất là ~2~ như sau:

  • Xuất phát từ ô ~(1,1)~, đi bộ sang ô ~(1,2)~, rồi đi bộ sang ô ~(1,3)~.

  • Nhảy từ ô ~(1,3)~ sang ô ~(1,6)~. Đi bộ từ ô ~(1,6)~ sang ô ~(2,6)~, rồi đi bộ sang ô ~(3,6)~.

  • Nhảy từ ô ~(3,6)~ sang ô ~(3,8)~ chứa kho báu.

• Ví dụ 2: Cách di chuyển có số lần nhảy nhỏ nhất là ~3~ như sau: Xuất phát từ ô ~(1,1)~, nhảy sang ô ~(1, 3)~, rồi nhảy sang ô ~(1,7)~, rồi nhảy sang ô ~(1,9)~ chứa kho báu.