题目描述

你的任务是对 $k = 1, 2, \cdots, n$ 的每一个 $k$ 计算出有多少种方案将两个骑士放在 $k \times k$ 的棋盘上，并且这两个骑士不会互相攻击。

提示：骑士的移动规则遵守国际象棋的规则，一个骑士每次可以垂直移动 $2$ 格、水平移动 $1$ 格，或者水平移动 $2$ 格、垂直移动 $1$ 格。如果一个骑士可以通过一次移动到达另一个骑士的位置，他们就会互相攻击。

输入格式

输入一个正整数 $n$。

输出格式

输出 $n$ 行，每行输出一个整数表示方案数。

样例

8

0
6
28
96
252
550
1056
1848

数据范围

• $1 \le n \le 10000$