在 n×n 格的棋盘上放置彼此不受攻击的 n 个皇后。
按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n皇后问题等价于再n×n的棋盘上放置 n 个皇后，任何 2 个皇后不在同一行或同一列或同一斜线上。
输入n，输出有多少种摆放方法。
第一行输入 。
输出方案总数。
样例输入
4
样例输出
2
来源[CCF NOI1149 N皇后问题]http://oj.noi.cn/oj/#main/show/1149