Superqueens P32445

A superqueen is a piece of chess that combines the movements of a queen and of a knight. Given an n, in how many ways can we place n superqueens on an n × n board in such a way that no superqueen threatens another superqueen? Here, we are only interested in positions that are really distinct, in the sense that cannot be obtained by rotating or reflecting another position. For instance, for n = 10 there is just one such solution:

Input

Input consists of several cases, each with an n between 1 and 20.

Output

For every case, print the number of distinct positions.