Problem G
How Many Pieces of Land?
Input: Standard Input
Output: Standard Output
Time Limit: 3 seconds

 

You are given an elliptical shaped land and you are asked to choose n arbitrary points on its boundary. Then you connect all these points with one another with straight lines (that’s n*(n-1)/2 connections for n points). What is the maximum number of pieces of land you will get by choosing the points on the boundary carefully?

 

Fig: When the value of n is 6.

 

Input

The first line of the input file contains one integer S (0 < S < 3500), which indicates how many sets of input are there. The next S lines contain S sets of input. Each input contains one integer N (0<=N<2^31).

 

Output

For each set of input you should output in a single line the maximum number pieces of land possible to get for the value of N.

 

Sample Input:

4
1
2
3
4

 

Sample Output:

1
2
4
8

---