Chính quyền thành phố Zagreb đã quyết định xây dựng một bãi đỗ xe mới. Để thực hiện điều này, họ sẽ sử dụng một khu đất hình chữ nhật, có thể coi là một ma trận với $N$ hàng và $M$ cột. Để thu hút khách hàng và tăng doanh thu, thị trưởng đã quyết định đặt các đài phun nước, giếng nước và các loại đài phun khác tại một số vị trí xác định trước trên khu đất. Các ô còn lại được dành cho việc di chuyển của phương tiện và sẽ được quy hoạch theo một trong hai khả năng: Ô đỗ xe, hoặc Ô dành cho phương tiện di chuyển tự do.

Các phương tiện có thể di chuyển trong bãi đỗ xe bằng cách di chuyển sang ô lân cận theo một trong bốn hướng (bắc, nam, đông hoặc tây). Bãi đỗ xe phải được xây dựng sao cho tại mọi thời điểm, từ mỗi vị trí đỗ xe đều có thể đi đến lối vào/lối ra của bãi đỗ xe nằm ở ô góc trên bên trái (giao điểm của hàng đầu tiên và cột đầu tiên). Nói cách khác, các phương tiện đang đỗ không được chặn đường ra của các phương tiện khác. Mỗi phương tiện đang đỗ phải có khả năng rời khỏi bãi đỗ xe mà không cần di chuyển các phương tiện khác.

Hãy giúp thị trưởng xác định số lượng chỗ đỗ xe tối đa có thể có cho khu đất đã cho.

Ghi chú: Ô ở hàng đầu tiên và cột đầu tiên là lối vào bãi đỗ xe, không dành cho việc đỗ xe và sẽ luôn luôn trống.

Dữ liệu vào

Dòng đầu tiên chứa các số nguyên dương $N$ và $M$ ($1 \le N \le 6, 1 \le M \le 100$), là số hàng và số cột của khu đất. $N$ dòng tiếp theo, mỗi dòng chứa $M$ ký tự mô tả khu đất: Ký tự ‘x’ biểu thị ô sẽ xây dựng đài phun nước, Các ô còn lại được đánh dấu bằng ký tự ‘.’ và sẽ được quy hoạch làm bãi đỗ xe.

Dữ liệu ra

In ra trên một dòng duy nhất số lượng chỗ đỗ xe tối đa có thể đạt được.

BODOVANJE

Ví dụ

Dữ liệu vào 1

3 3
...
.x.
...

Dữ liệu ra 1

2

Dữ liệu vào 2

3 3
...
..x
...

Dữ liệu ra 2

4

Dữ liệu vào 3

3 6
.x..x.
..x.x.
......

Dữ liệu ra 3

3

Dữ liệu vào 4

4 5
....x
....x
..x..
.x..x

Dữ liệu ra 4

7

Ghi chú

Giải thích ví dụ thứ tư: một cách sắp xếp chỗ đỗ xe khả thi:

.PPPx
....x
.Px.P
PxP.x