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\) \((1 \leq n \leq 10000)\).

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.

Example

8

0
6
28
96
252
550
1056
1848