Nhiệm vụ của bạn là với mỗi số \(k = 1, 2, \ldots, n\), đếm số cách đặt hai con mã trên bàn cờ vua \(k \times k\) sao cho bọn chúng không tấn công được nhau (trong một bước).

Input

• Chỉ một dòng duy nhất chứa số tự nhiên \(n\).

Output

• In \(n\) dòng. Mỗi dòng gồm một số nguyên dương là kết quả của bài toán.

Constraints

• \(1 \le n \le 10000\)

Example

Sample input

8

Sample output

0
6
28
96
252
550
1056
1848