Squares in a grid square

Time limit2sMemory limit512 MB

Summary

For each grid side length l, count every square whose sides lie along grid lines, including tilted ones.

Level: Easy3 of 10
Topics: Math, Combinatorics, Implementation
Solved: No attempts yet

Problem

The game "La cave aux énigmes" asks how many squares are contained in a grid square whose side has length $l$ . A grid square of side length 4 looks like this.

Thirty squares are visible in that picture. Count every square visible in the picture of a grid square of side length $l$ .

Input

The first line contains the number of test cases $P$ . ( $1 \le P \le 1000$ )

Each of the next $P$ lines contains one side length $l$ of a grid square. ( $1 \le l \le 999999$ )

Output

For each $l$ , print the number of squares visible in the picture of a grid square of side length $l$ , one per line. The answer can exceed the range of a 32-bit integer, so use 64-bit integers.

Examples1

Example 1
Input
```
4
1
2
3
4
```
Expected output
```
1
5
14
30
```