Migrated from Lutece 400 Sawthooth II

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

There is a romantic line called sawthooth II which consists of two parallel infinite half-lines joined by a straight segment. It looks like a character Z. You are given $N$ Z lines, can you calculate the maximum number of regions they can divide the plane?

Input

The first line is an integer $T$ which stands for the number of test cases. Then it follows $T$ test cases. Each test case has only one line contains only one integer $N$ ($0\leq N\leq 10^9$).

Output

For each test case, print one line containing an integer which stands for the maximum number of regions they can divide the plane.

Samples

2
1
2

2
12

Resources

10th SCU Programming Contest Final