Alice is very interested in the algorithm. He finds a interesting book called "Algorithmic puzzles" which contains more than 100 puzzles. The puzzles included many typical algorithmic thinking in the programming. He likes the grid puzzles most. The grid puzzle is which the puzzle is based on the grids.
On the page 173, Alice is attracted by a grid puzzle. There is a N * N grids. Each grid should be filled with a number from 1, 2, .., N * N. No two girds share the same number. For any two adjacent numbers X and X + 1, the grids they filled in should also be adjacent. The problem is to find the maximum sum of the numbers in the main diagonal (the ith grid in the ith row). Alice wants you to help him solve the problem.
Input
There are multiple test cases. For each test case:
There is an integer N (1 <= N <= 1000) which described above.
Output
For each test case, output the maximum sum of the numbers in the main diagonal.
Sample Input
2
3
Sample Output
6
19
