1895: 猛兽监狱

【题目描述】

关猛兽的笼子是一个长、宽不超过4×4的正方形，里面设有一些障碍，每个笼子里关着的猛兽脾气都很大，只要两只位于猛兽位于同一行或同一列即会发生冲突，但障碍物可以阻挡同行或同列猛兽的冲突。问最多可关几个猛兽而不会发生冲突。

如下图所示，左边表示初始笼子，右边b-e显示了四种关猛兽的方案(猛兽以实心圆表示)，当然，最后两个方案d、e是错误的。

【输入格式】

输入多组测试数据，每组测试数据的第1行为一个整数N，表示笼子的大小。

随后N行N列为描述笼子初始状态的字符，其中“.”描述笼子，“X”表示障碍物。

所有测试数据结束的标志为0.

【输出格式】

每组数据输出占一行，表示最多可放猛兽的数量。

【输入样例】

4

.X..

....

XX..

....

3

.X.

X.X

.X.

3

...

.XX

.XX

0

【输出样例】

5

5

2

输入多组测试数据，每组测试数据的第1行为一个整数N，表示笼子的大小。

随后N行N列为描述笼子初始状态的字符，其中“.”描述笼子，“X”表示障碍物。

所有测试数据结束的标志为0.

4

.X..

....

XX..

....

3

.X.

X.X

.X.

3

...

.XX

.XX

0

5
5
2