1084 - N皇后问题
Description

在 n*n 格(n<=8)的国际象棋棋盘上摆放 n 个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。


Input
一行一个正整数,表示 n


Output
输出一个正整数,表示n皇后摆放的个数


Examples

Input

8

Output

92
题目参数
Time Limit 1 second
Memory Limit 128 MB
提交次数 1
通过次数 1