Your task is to count for ~k = 1, 2, \ldots, n~ the number of ways two knights can be placed on a ~k \times k~ chessboard so that they do not attack each other.

Input

• The only input line contains an integer ~n~.

Output

• Print ~n~ integers: the results.

Constraints

• ~1 \le n \le 10000~

Example

Sample input

8

Sample output

0
6
28
96
252
550
1056
1848