题目描述

小青遇到了这样一个问题：按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。在n×n格的棋盘上，已经摆放好其它的一些棋子，皇后与皇后之间如果有棋子，就不能相互攻击，求出在n×n的棋盘上可以摆放最多的相互不能攻击的皇后数。

输入格式

首先输入n（n<=4），然后输入n×n的棋盘，”X”表示已经摆放了的棋子，”.”表示棋盘空位。

输出格式

输出最多能摆放的皇后数。 4 .X.. .... XX.. .... 2 XX .X 3 .X. X.X .X. 3 ... .XX .XX 4 .... .... .... ....

样例

样例 1

输入 # 1

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

输出 # 1

4
1
2
2
4