Keshri has organized a party for his friends at his home. There are a total of n people present in the party.

Everyone is excited to meet other people and enjoy the party. Each person makes a handshake with every other person in the hall. 

While watching all these happening, Keshri asked you to count the number of distinct handshakes which occurred during the party. Since the number of people in the party is large, it is not possible for you to reach every pair and count the number of handshakes.

Also, if you are not able to solve Keshri's question, then he may eat your piece of Cake (He is crazy!!!).

Help yourself to get the piece of Cake you deserve.

Input:

First line contains t - the number of test cases. Each of the next t lines contains a single integer n - the total number of people present at the party.

Output:

Print t lines, each line containing the answer to the problem for each test case.

Constraints:

1 <= t <= 1000
2 <= n <= 10000

Problem Setter:

Devesh Jagwani