题目描述

Scientists have discovered a new species of bacteria and have begun conducting experiments to study it.

In one of the experiments, they placed a colony of bacteria on an infinite grid, and it turned out that it expands every second. In every even second, the colony expands in eight directions, meaning it occupies cells adjacent to the occupied ones both orthogonally and diagonally, if they are not already occupied. In odd seconds, it only expands in four directions, occupying cells adjacent to the occupied ones orthogonally.

Help the scientists determine how many cells are occupied by the colony of bacteria at the $k$-th second of the experiment, given that it was placed on the grid in the first second.

输入格式

The first line contains an integer $k$ --- the time in seconds when the scientists want to know how many cells are occupied by the colony of bacteria ($1 \le k \le 10^8$).

输出格式

Output a single number -- the number of cells occupied by the colony of bacteria at the $k$-th second of the experiment.

1

1

2

9

3

21

4

45

5

69

提示

The filling of the grid for the first five seconds, with the cell indicating the second when this cell will first be occupied by the colony of bacteria.

$$\begin{array}{ |c|c|c|c|c|c|c|c|c| } \hline & & 5 & 5 & 5 & 5 & 5 & & \\ \hline & 5 & 4 & 4 & 4 & 4 & 4 & 5 & \\ \hline 5 & 4 & 4 & 3 & 3 & 3 & 4 & 4 & 5 \\ \hline 5 & 4 & 3 & 2 & 2 & 2 & 3 & 4 & 5 \\ \hline 5 & 4 & 3 & 2 & 1 & 2 & 3 & 4 & 5 \\ \hline 5 & 4 & 3 & 2 & 2 & 2 & 3 & 4 & 5 \\ \hline 5 & 4 & 4 & 3 & 3 & 3 & 4 & 4 & 5 \\ \hline & 5 & 4 & 4 & 4 & 4 & 4 & 5 & \\ \hline & & 5 & 5 & 5 & 5 & 5 & & \\ \hline \end{array}$$