You are probably well-known classical problem of placing queens: a chessboard N
×N
is required to place N
queens so that no two queens beat each other. This arrangement is called a peaceful queens. However, in this problem we are interested in is not some kind of a peaceful arrangement of the queens, and all the various peace arrangement. More precisely, their total number. For example, for 8×8 board there are 92 different peaceful arrangement of queens.
The input file is written only natural number N
(N ≤ 12
).
The output file output the desired number of peaceful arrangements of queens.