Nghe nói xu hướng thời trang mới nhất là những con bò có hai đốm trên da, Farmer John đã mua cả một đàn bò hai đố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 hai đố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\) (\(1 \leq N, M \leq 50\)) như sau:

................
..XXXX....XXX...
...XXXX....XX...
.XXXX......XXX..
........XXXXX...
.........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 hai đốm. Mọi con bò trong đàn của FJ đều có đúng hai đốm.

FJ muốn dùng ít sơn nhất có thể để hợp nhất hai đố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 ba 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....

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 hai đố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.

\(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....

3

................
..1111....222...
...1111....22...
.1111......222..
........22222...
.........222....

................
..1111....222...
...1111X...22...
.1111..XX..222..
........22222...
.........222....

Nguồn

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

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