题目描述

给你一个大小为 $n×n$ 的棋盘。最初，棋盘上的每个单元格都包含一个图形。

在一次移动中，您可以选择某个单元格中显示的一个图形，并将其移动到与当前单元格共享边或角的单元格之一，即从单元格 $(i,j)$ 您可以将图形移动到单元格中：$(i−1,j−1);(i−1,j);(i−1,j+1);(i,j−1);(i,j+1);(i+1,j−1);(i+1,j);(i+1,j+1)$ $8$ 个方位; 当然你不能将其移动到棋盘外面。

你现在需要计算最少多少步能将棋盘上的图形全都移动到一个单元格中（即 $n²-1$ 个单元格没有图形，一个单元格上有 $n²$ 个图形）

输入格式

多组输入

输入一个整数$n$代表棋盘的大小 $1 \leq n \leq 5*10^5$

输出格式

输出一个数字代表将所有图形移到一个单元格所需的最少移动次数。

1
5
9
101

0
40
240
343400