Herbert

Time limit1sMemory limit128 MB

Summary

Count distinct squares a robot starting at the origin can end on within n moves when each step or ninety-degree turn costs one move.

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

Problem

Herbert is a game where you drive one robot across an infinite two dimensional grid. Three commands are available.

s: move one square forward in the direction the robot currently faces.
l: turn ninety degrees counterclockwise without leaving the square.
r: turn ninety degrees clockwise without leaving the square.

Every command spends one move, turns included. The robot starts at the origin facing one fixed direction.

After playing for a while you start to wonder how many squares the robot can reach once the number of moves is capped. Given a budget of at most $n$ moves, count the distinct squares the robot can end up on.

Input

The first line has an integer $t$ ( $1 \le t \le 100$ ), the number of test cases.

Each of the next $t$ lines has one integer $n$ ( $0 \le n \le 10^9$ ), the largest number of moves allowed in that test case.

Output

For each test case, print the number of reachable squares on its own line.

Examples1

Example 1
Input
```
4
0
1
2
3
```
Expected output
```
1
2
5
11
```