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.

Input

The input file is written only natural number N (N ≤ 12).

Output

The output file output the desired number of peaceful arrangements of queens.