How Many Pieces of Land?

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 <231). 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

2/2 8