思路

暴力$O(n^3)$不可取.我们先扫描一遍棋盘。用$r,c$ 数组来统计第i行/第i列有多少个皇后。对于处于同一正副对角线的两点，有如下规律:

正对角线：两点的横纵坐标之差x-y相等.所以用x-y来对正对角线编号

副对角线：两点的横纵坐标之和相等.所以用x+y来对正对角线编号

所以再使用$x,y$ 数组来记录第i个正负对角线的皇后个数。

题目内容

米小游是一个热衷于国际象棋的棋手，他最近在研究 $n$ 皇后问题。在国际象棋中，皇后是一种强大的棋子，能够沿着横、竖、斜线攻击其他棋子。

而在 $n$ 皇后问题中，皇后也是一种强大的棋子，它能攻击同一行、同一列以及同一 $45$ 度角斜线和 $135$ 度角斜线上的其他皇后。

米小游手上拿着一个 $n\times n$ 的棋盘，上面已经放置了一些皇后。他希望再放置一个皇后，使得所有的皇后不会互相攻击。

对于一个 $n\times n$ 的棋盘，有多种不同的摆放皇后的方式，而有些摆法可能会导致皇后之间发生攻击，有些摆法则不会。

因此，米小游需要找到所有满足条件的摆法，以便让他更好地研究 $n$ 皇后问题，你能帮米小游求出有多少种放置方案吗？

输入描述

第一行输入一个正整数 $n$ ，代表棋盘大小。

接下来的 $n$ 行，每行输入一个仅由 $.$ 和 $*$ 组成的字符串，其中 $*$ 代表放置了一个皇后， $.$ 代表未放置皇后。

保证输入的棋盘中没有两个皇后会互相攻击。

$1\le n\le 1000$

输出描述

输出米小游有多少种放置方案。

样例

输入

3
.*.
...
...

输出

2