A triangle made of coins of height h is as follows
It has h coins at the base and h-1 coins one level above base and so on.(Coins are placed as shown in the figure below)
And at the top most level there will be only one coin
Now given h the task is to invert this triangle by moving minimum number of coins.

For example when h=4 triangle is

For h=4 at least 3 coins must be moved to invert it.

Input

In the first line N will be given and then N lines follow with each line having a integer which is the height of triangle in that test case.00≤h<10¹⁰;

Output

For each test case output in a seperate line the minimum number of moves required to invert the triangle. Output fits in long long data type

Example

Inputt:
1
3

Output:
2