410227: GYM103987 C Make it in a Line

The game Tic-Tac-toe is played by two people taking turns on a $$$3 \times 3$$$ board, with the person winning the game when his first getting a whole horizontal or vertical or diagonal line filled with his tokens. It's easy to find that there are only $$$8$$$ ways of putting tokens to win the game (only considering the tokens in the key line).

All $$$8$$$ winning ways are shown in the picture below.

Today, Walk_alone is bored with playing the 2D Tic-Tac-Toe with Salix Leaf! He thinks the board is too small and the winning ways are too monotonous. So they decide to make a larger chess board and add a brand new dimension to the game! Now this game seems more interesting:

In a 3D $$$n \times n \times n$$$ cube, two people put their tokens by turn, and the first one whose tokens fill one horizontal or vertical or diagonal line of the cube wins the game. For instance, some winning ways in a 3D $$$4 \times 4 \times 4$$$ cube are shown in the picture below.

He is too lazy to do any calculation, so he wants you to tell him the number of ways to put the tokens in a line.

The first and the only line of the input contains an integer $$$n\ (2 \leq n \leq 1000)$$$.

Print only one number representing the number of ways to put the tokens in a line.

The problem contains $$$20$$$ test cases. You can get $$$5$$$ points for each passed test case.

2

28

3

49

4

76