A trading venue has n participants. Any two participants may maintain a bilateral trading relationship. The venue's surveillance rules forbid circular trading among any three parties: no three participants may all pairwise trade with each other.

Compute the maximum possible number of bilateral trading relationships, as an exact integer. Answer q independent queries.

Input

The first line contains q. Each of the next q lines contains one integer n.

Output

For each query, output the maximum number of bilateral trading relationships on its own line.

Constraints

1 <= q <= 10^4 1 <= n <= 10^18

Scoring

This is a standard problem: a submission scores full points if it produces the correct output for every test case, and zero otherwise.