Ваше завдання полягає в тому, щоб для ~k=1,2,\ldots,n~ порахувати кількість способів, якими два коня можуть розташуватися на ~k \times k~ шахівниці так, щоб вони не атакували один одного.

Обмеження

• ~1 \le n \le 10000~

Формат вхідних даних

Єдиний рядок містить ціле число ~n~.

Формат вихідних даних

Вивести ~n~ цілих чисел: результати.

Приклад вхідних даних

8

Приклад вихідних даних

0
6
28
96
252
550
1056
1848