C. Dalgona Challenge
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

In the Dalgona Challenge from Squid Game, players must carefully carve out a shape from a honeycomb candy using a needle. The Masked Guards have designed a new version of this challenge using laser-cut patterns on a circular honeycomb.

You are g iven a circular honeycomb with $$$n$$$ points along its boundary. The guards use laser cutters to draw a straight line between every pair of these points. That is, for every possible pair of distinct points, a straight laser cut is made, linking each point with every other point. These laser cuts create a complex pattern of intersecting lines that divide the honeycomb into multiple regions.

Your task is to determine the maximum number of regions the honeycomb can be divided into when all possible laser cuts are made.

Input

The first line contains the number of test cases $$$t$$$ ($$$1 \leq t \leq 10^{5} $$$).

Each test case contains :

A single integer $$$n$$$ ($$$0 \leq n \leq 10^{5}$$$), representing the number of points.

Output

A single integer, the maximum number of regions formed in the honeycomb.

Example
Input
3
1
4
6
Output
1
8
31
Note

In the first two testcases, the result is obvious.

In the third testcase, it can be proven that the maximum number of regions obtained after placing 6 points in the circle optimally is $$$31$$$

test case 3 .