Peaceful Queens - 2

Given a natural number n, determine how many distinct ways there are to place n queens on an n×n chessboard such that no two queens threaten each other. Arrangements that are identical when the board is rotated or reflected are considered the same.

Input

The input consists of a single natural number n, where n does not exceed 10.

Output

Output a single integer: the number of unique arrangements of non-attacking queens on the n×n chessboard.

Examples