You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

一个骑士的攻击位置如下所示：

你的任务是计算 k=$1,2\ldots n$，即两个骑士在一个k*k的棋盘上不相互攻击的方式。

骑士走法和中国象棋的马相同，同样是走“日”字，或英文字母大写的“L”形：即先向左（或右）走1格，再向上（或下）走2格；或先向左（或右）走2格，再向上（或下）走1格。国际象棋的骑士没有“绊馬脚”的限制，故骑士可越过其他棋子。

输入

唯一的输入行包含一个整数n。

输出

打印n整数：结果。

约束

• $1 \le n \le 10000$

Example

Input:

8

Output:

0
6
28
96
252
550
1056
1848