Giải bài trực tuyến

Cho 1 bàn cờ kích thước NxN. Hãy đếm số quân tượng nhiều nhất có thể đặt lên bàn cờ sao cho cùng lúc không có 2 quân tượng nào ăn được nhau. Quân tượng đi theo luật cờ vua thông thường với ngoại lệ : chúng không thể thực hiện nước đi dài quá 1 ô. Nói cách khác, nếu quân tượng đang đứng ở ô (u,v) thì có thể đi được đến ô (u±1,v±1).

Ngoài ra 1 số ô của bàn cờ có vật cản và không thể đặt quân cờ lên.

Input

- Dòng đầu số N (1<=N<=50)

- N dòng sau mỗi dòng N kí tự mô tả bàn cờ. Kí tự '*' thể hiện ô có vật cản, kí tự '.' thể hiện ô trống.

Output

- Số quân tượng nhiều nhất có thể đặt lên bàn cờ

Sample input

3

*.*

.*.

***

Sample output

2