Our meme-lord Varun is a stud guy. One day, his girlfriend is stuck in a chamber which has a sequence lock of n distinct digits starting from 1 to n in a fixed order. Now, to prove that his love is true, he has to get her out in any case.
Varun doesn't know the correct sequence but he is very smart. So, just to keep her calm, in the beginning itself, he tells her that she won't be stuck in for more than a certain time. Now, he has to find the maximum time it would take him to find the correct sequence.

Initially, all buttons of the lock are unpressed. To unlock one needs to press the sequence lock in correct order. The pattern lock is such that, let's say the correct sequence is {3,1,2}, then if he presses 1 first, the door remains locked and the first button is unpressed immediately(no extra time) . Now if he presses 3 for the first place and 2 for the second, (which is another wrong attempt), both would be unpressed immiediately.

It is given that it takes him 1 second to press each button.

Help him find the maximum time(in seconds) for which she has to remain in(consider the time taken to open the door and unpress any button as negligible). 

Input:

The first line contains

T - Number of test cases 

Each test case contains a single line input - 

N -  number of digits in the lock

Output:

For each test case output the maximum time (in seconds)

Constraints:

T<=1000

1<=n<=3000