Cho bàn cờ vua kích thước \(n\)x\(n\). Trên bàn cờ có một số ô có chướng ngại vật ngăn cản các quân xe nhìn thấy nhau và "ăn" nhau. Tìm số lượng quân xe lớn nhất có thể đặt trên bàn cờ cho trước sao cho không có 2 quân xe nào có thể "ăn" nhau.

Ví dụ về 1 bàn cờ vua \(4\)x\(4\) với số lượng quân xe lớn nhất có thể đặt là \(5\):

Input: Có nhiều bộ test.

Mỗi bộ test bắt đầu với số \(n\) (\(1 \le n \le 4\)). Theo sau là \(n\) dòng, mỗi dòng mô tả 1 dòng trên bàn cờ với "." là ô trống và "X" là ô có chướng ngại vật.

Input kết thúc với \(n=0\).

Output: Với mỗi bộ test, output trên 1 dòng số lượng quân xe lớn nhất có thể đặt trên bàn cờ đó mà không có 2 quân xe nào có thể "ăn" nhau.

Input mẫu

4
.X..
....
XX..
....
2
XX
.X
3
.X.
X.X
.X.
3
...
.XX
.XX
4
....
....
....
....
0

Output mẫu

5
1
5
2
4