P13964 [VKOSHP 2024] Colony of Bacteria

科学家发现了一种新的细菌种类，并开始进行实验研究。 在一次实验中，他们将一个细菌群落放置在一个无限网格上，发现该群落每秒都会扩张。在偶数秒时，菌落会向八个方向扩张，即占据与已占据单元格正交和对角相邻的所有未占据单元格；在奇数秒时，菌落仅向四个正交方向扩张。 已知细菌在第一秒被放置于网格上，请帮助科学家计算在第 $k$ 秒时被细菌占据的单元格数量。第 $1$ 秒细菌不扩张。

第一行包含一个整数 $k$，表示科学家想知道细菌占据单元格数量的时间点（$1 \le k \le 10^8$）。

输出一个数字，表示第 $k$ 秒时被细菌群落占据的单元格数量。

前五秒的网格填充情况（单元格数字表示该单元格首次被细菌占据的秒数）： $$\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}$$