chessdatxe

Trong cờ vua, quân xe là quân cờ có thể di chuyển bất kỳ số ô nào theo chiều dọc hoặc chiều ngang.

Trong bài toán này, chúng ta sẽ xem xét những bàn cờ nhỏ (tối đa là 4 × 4) có thể chứa những bức tường mà quân xe không thể di chuyển qua.

Mục tiêu là đặt càng nhiều quân xe lên bàn cờ càng tốt sao cho không có quân xe nào có thể bắt được nhau.

Một cấu hình quân xe được coi là hợp lệ với điều kiện không có hai quân xe nào nằm trên cùng một hàng ngang hoặc cột dọc trừ khi có ít nhất một bức tường ngăn cách chúng.

Hình ảnh sau đây hiển thị năm hình ảnh của cùng một bảng. Hình ảnh đầu tiên là bảng trống, hình ảnh thứ hai và thứ ba hiển thị cấu hình hợp lệ, và hình ảnh thứ tư và thứ năm hiển thị cấu hình bất hợp lệ.

Đối với bàn cờ này, số lượng quân xe tối đa trong một cấu hình hợp lệ là 5; hình ảnh thứ hai cho thấy một cách để thực hiện, nhưng vẫn còn nhiều cách khác.

Nhiệm vụ của bạn là viết một chương trình tính toán số quân xe tối đa có thể đặt trên bàn cờ theo cấu hình hợp lệ khi được cung cấp mô tả về một bàn cờ.

Đầu vào

Dòng đầu tiên của dữ liệu đầu vào là số lượng trường hợp thử nghiệm. Mỗi trường hợp thử nghiệm chứa mô tả về bảng.

Mỗi mô tả về bàn cờ bắt đầu bằng một dòng chứa số nguyên dương N là kích thước của bàn cờ; N tối đa là 4.

N dòng tiếp theo, mỗi dòng mô tả một hàng của bảng, với dấu '.' biểu thị một khoảng trống và chữ 'X' viết hoa biểu thị một bức tường. Không có khoảng trống nào trong tệp đầu vào.

Đầu ra

Đối với mỗi trường hợp thử nghiệm, đưa ra một dòng chứa số quân xe tối đa có thể đặt trên bàn cờ theo cấu hình hợp lệ.

Lưu ý rằng dòng đầu ra đầu tiên của mỗi trường hợp thử nghiệm phải là Trường hợp #tn, trong đó tn là số trường hợp thử nghiệm.

Mẫu đầu vào

.X..

....

XX..

....

.X.

...

.XX

....