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:

largeboard,
showmover=false,
label=false,
maxfield=j10,
setpieces=qc1,qf2,qi3,qa4,qd5,qg6,qj7,qb8,qe9,qh10
boardfontsize=20pt

Input

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

Output

For every case, print the number of distinct positions.

Public test cases

**Input**

4 10 11 12 16 20

**Output**

0 1 6 22 25411 61984976

Information

- Author
- Salvador Roura
- Language
- English
- Official solutions
- C++
- User solutions
- C++