Two Knights

Source: CSES

Version: Phuoc Hung OJ Extended

Problem Statement

Consider a square chessboard of size $k\times k$. Place two knights on distinct squares so that neither can attack the other in one knight move. A knight moves two squares along one axis and one square along the other. Swapping the two identical knights does not create a new placement. Given $n$, compute the number of valid placements for each $k=1,2,\ldots,n$.

Input

One line contains the positive integer $n$, the largest board size to consider.

Output

Print $n$ lines. Line $k$ contains the number of non-attacking placements on a $k\times k$ board.

Subtasks

• Subtask 1 (20%): $1\\le n\\le20$.
• Subtask 2 (30%): $1\\le n\\le200$.
• Subtask 3 (50%): $1\\le n\\le10000$.

Examples

Example 1

Input:

3

Output:

0
6
28

Explanation: A 1-by-1 board has no pair of squares. A 2-by-2 board has 4 choose 2 = 6 pairs, all safe. A 3-by-3 board has 36 pairs of squares, of which 8 are attacking pairs, leaving 28.

Example 2

Input:

1

Output:

0

Explanation: There is only one square, so two knights cannot occupy distinct squares.

Example 3

Input:

4

Output:

0
6
28
96

Explanation: For k=4 there are 120 unordered pairs and 24 attacking pairs, giving 96. The previous three lines correspond to sizes 1, 2, and 3.