题目描述

著名的N皇后问题，需在N×N棋盘上放置N个皇后，要求任意两个皇后不在同一行、同一列、同一斜线上（互相无法攻击）。棋盘上*表示该位置可放置皇后，.表示该位置不可放置皇后。

输入描述

第一行有一个整数N。接下来N行，每行包含N个字符，描述棋盘状态。

输出描述

输出合法的放置方案总数。

输入样例1

4
**.*
****
****
****

输出样例1

1