题目描述

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

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

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

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

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

输入描述

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

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

$1\le n\le 1000$

输出描述

输出薯条哥有多少种放置方案。如果给定的输入的棋盘中有两个皇后会互相攻击，则输出-1。

样例1

输入

3
. * .
. . .
. . .

输出

2

说明 只有左下角和右下角两个位置可以放置。

样例2

输入

3
. * .
. * .
. . .

输出

-1