N-Queen

Interview

Time limit10sMemory limit128 MB

Summary

Count the ways to place N non-attacking queens on an N by N board for N under 15.

Level: Medium5 of 10
Topics: Backtracking, Bit manipulation
Solved: No attempts yet

Problem

The N-Queen problem asks for placements of $N$ queens on an $N \times N$ chessboard in which no queen attacks another. A queen attacks every other queen in its row, in its column, and on its diagonals.

Given $N$ , write a program that counts the placements of the $N$ queens. Placements that coincide after a rotation or a reflection are counted separately.

Input

The first line contains $N$ ( $1 \le N < 15$ ).

Output

Print the number of placements of $N$ queens in which no queen attacks another.

Examples1

Example 1
Input
```
8
```
Expected output
```
92
```