Nhiệm vụ của bạn là: với mỗi ~k = 1, 2, ..., n,~ hãy đếm số cách đặt 2 quân mã trên bàn cờ kích thước ~k × k~ sao cho chúng không tấn công nhau.

Dữ liệu vào: Dòng đầu tiên chứa một số nguyên ~n~ — kích thước tối đa của bàn cờ.

Dữ liệu ra: In ra ~n~ số nguyên, mỗi số ứng với số cách đặt 2 quân mã không tấn công nhau trên bàn cờ kích thước từ 1×1 đến ~n×n~.

Ràng buộc:

~1≤n≤10^4~

Ví dụ :

Input:

8

Output:

0  
6  
28  
96  
252  
550  
1056  
1848