题目描述

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

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

输入格式

第一行包含一个正整数 $n$。

输出格式

输出 $n$ 行，第 $k$ 行包含一个整数，表示在 $k \times k$ 的棋盘上放置两个互不攻击的骑士的方案数。

样例

8

0
6
28
96
252
550
1056
1848

数据范围与提示

• $1 \le n \le 10000$