Cho bảng \(w \times h\) gồm các ký tự . và #. Một con robot xuất phát từ vị trí \((1, 1)\) muốn đi đến vị trí \((w, h)\), nó chỉ có thể di chuyển trên các ô có ký tự . và chỉ di chuyển từ một ô sang các ô kề cạnh với ô đó và không vượt qua giới hạn của bảng.

Yêu cầu: Tìm cách đặt một hình vuông có kích thước nhỏ nhất lên bảng đã cho, hình vuông chỉ được đặt trên các ô có ký tự . sao cho con robot không thể di chuyển đến vị trí \((w, h)\). Ngoài ra hình vuông không được phủ lên ô \((1, 1)\) và ô \((w, h)\).

Input

• Dòng đầu tiên chứa \(2\) số nguyên \(w\) và \(h\) (\(2 \le w, h \le 1500\)).
• Mỗi dòng trong \(h\) dòng sau chứa xâu độ dài \(w\) từ các ký tự trong tập {#, .}.

Output

• Ghi ra một số là độ dài cạnh nhỏ nhất của hình vuông cần đặt vào bảng. Nếu không thể chặn được robot thì in ra Impossible.

Example

11 6
......#####
.#.#...#..#
.#.#.......
.......###.
#####.###..
#####......

2