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.

题目描述

Kitten 最近玩的“有限冷冷”出了一个五子棋小游戏，他不擅长五子棋，于是让 Csvoner 帮忙。

Csvoner 想到了一个经典的五子棋阵法，只要这个阵法的阵眼上都是自己的棋子，就不可能输。

更具体的，$n$ 路棋盘是由 $n$ 条横线和 $n$ 条竖线构成的。共有 $n\times n$ 个可以下棋的位置。我们用 $(i,j)$ 表示第 $i$ 行第 $j$ 列的位置。

这个阵法的关键在于，棋盘中至少有一个己方棋子，如果 $(x,y)$ 的位置有己方棋子，那么 $(x-2,y-1),(x-1,y+2),(x+1,y-2),(x+2,y+1)$ 这四个位置如果在地图内，则必须也有己方棋子。

显然一个固定大小的棋盘可以有多种阵法方案，请你算算对于 $n\times n$ 的棋盘，最少需要多少个己方棋子可以完成布阵。

输入格式

一个数 $n$。

输出格式

一个数，即最少需要多少个己方棋子可以完成布阵。

5

5

9

16

样例解释

$5$ 路棋盘有多种摆法，但都至少要 $5$ 枚旗子。

下面是 $9$ 路棋盘两种摆法，需要的棋子数量分别为 $16$ 与 $17$。

数据规模与约定

对于 $100\%$ 的数据，$5 \le n \le 10^7$。

• 子任务 1（30 分）：保证 $n\le 10$。
• 子任务 2（30 分）：保证 $n\le 100$。
• 子任务 3（40 分）：没有特殊限制。