题目描述

在国际象棋中，车是一种可以在垂直或水平方向上移动任意格数的棋子。在这个问题中，我们将考虑小型的国际象棋棋盘（最大为$4x4$），棋盘上可能存在墙，车不能穿过这些墙移动。目标是在棋盘上放置尽可能多的车，使得任意两个车都不能相互吃掉。一种合法的车的摆放配置是指，除非至少有一堵墙将它们隔开，否则任意两个车不能处于同一水平行或同一垂直列上。

下面的图片展示了同一个棋盘的五张图像。第一张图片是一个空棋盘，第二张和第三张图片展示了合法的摆放配置，第四张和第五张图片展示了不合法的摆放配置。对于这个棋盘，合法配置中车的最大数量是$5$；第二张图片展示了一种摆放方式，但还有其他几种方式。

你的任务是编写一个程序，给定一个棋盘的描述，计算出在合法配置下可以放置在棋盘上的车的最大数量。

输入

输入包含一个或多个棋盘描述，后面跟着一行包含数字0的行，该数字表示文件结束。每个棋盘描述以一行包含一个正整数$n$开始，$n$是棋盘的大小；$n$最大为$4$。接下来的$n$行每行描述棋盘的一行，用“.”表示空格，用大写字母“X”表示墙。输入中没有空格。

输出

对于每个测试用例，输出一行，包含在合法配置下可以放置在棋盘上的车的最大数量。

输入示例

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

输出示例

5
1
5
2
4

来源

1998年美国中北部地区竞赛