Hai quân mã

Nguồn: CSES Problem Set

Đề bài

Với mỗi giá trị $k=1,2,\ldots,n$, hãy xác định số cách đặt hai quân mã trên một bàn cờ kích thước $k\times k$ sao cho hai quân mã không tấn công nhau.

Hai cách đặt được xem là khác nhau nếu tập hợp hai ô được chọn để đặt quân mã là khác nhau.

Input

Dòng duy nhất chứa số nguyên $n$.

Output

In ra $n$ số nguyên, mỗi số trên một dòng.

Với mỗi $k=1,2,\ldots,n$, dòng thứ $k$ chứa số cách đặt hai quân mã trên bàn cờ kích thước $k\times k$ sao cho chúng không tấn công nhau.

Subtask

• Subtask 1 — 20%: $1 \le n \le 30$.
• Subtask 2 — 30%: $1 \le n \le 200$.
• Subtask 3 — 50%: $1 \le n \le 10^4$.

Ví dụ

Input

8

Output

0
6
28
96
252
550
1056
1848