题目描述

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

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

更具体的，$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 分）：没有特殊限制。