Nghe nói xu hướng thời trang mới nhất là những con bò có ba đốm trên da, Farmer John đã mua cả một đàn bò ba đốm. Không may, các xu hướng thời trang thường thay đổi rất nhanh, và mốt thịnh hành nhất hiện nay lại là bò chỉ có một đốm!

FJ muốn giúp đàn bò của mình hợp thời hơn bằng cách sơn từng con sao cho ba đốm của nó hợp thành một. Da của một con bò được biểu diễn bằng một lưới ký tự kích thước \(N \times M\) như sau:

................
..XXXX....XXX...
...XXXX....XX...
.XXXX......XXX..
........XXXXX...
..XXX....XXX....

Ở đây, mỗi ký tự X biểu thị một phần của một đốm. Hai ký tự X thuộc cùng một đốm nếu chúng kề nhau theo chiều dọc hoặc chiều ngang (kề nhau theo đường chéo không được tính), vì vậy hình trên có đúng ba đốm. Mọi con bò trong đàn của FJ đều có đúng ba đốm.

FJ muốn dùng ít sơn nhất có thể để hợp nhất ba đốm thành một. Trong ví dụ trên, ông có thể làm được điều này bằng cách chỉ sơn thêm bốn ký tự X (các ký tự mới được đánh dấu bằng * bên dưới để dễ nhìn hơn).

................
..XXXX....XXX...
...XXXX*...XX...
.XXXX..**..XXX..
...*....XXXXX...
..XXX....XXX....

Hãy giúp FJ xác định số ký tự X mới ít nhất mà ông phải sơn để hợp nhất ba đốm thành một đốm lớn.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên \(N\) và \(M\) cách nhau bởi dấu cách (\(1 \leq N, M \leq 50\)).

\(N\) dòng tiếp theo, mỗi dòng chứa một xâu độ dài \(M\) gồm các ký tự X và ., mô tả một hàng trong họa tiết trên da bò.

Dữ liệu ra

In số ký tự X mới ít nhất cần thêm vào họa tiết đầu vào để thu được một đốm duy nhất.

Ví dụ

6 16
................
..XXXX....XXX...
...XXXX....XX...
.XXXX......XXX..
........XXXXX...
..XXX....XXX....

4

Nguồn

USACO 2011 November Contest, Silver Division — Cow Beauty Pageant (Silver Level). Tác giả đề: Brian Dean.

https://usaco.org/index.php?page=viewproblem2&cpid=88