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.)
• At the top-most level there will be only one coin.

Now given h, the task is to invert this triangle by moving the 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. (0 ≤ h < 10¹⁰.)

Output

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

Example

Input:
1
3

Output:
2