Roy is on family trip to egypt there he saw a piramid of height H.which looks like follows.

Each of the brick is numbered starting from 1 starting with left to right and bottom to top also given that each brick has height 1 units. You need to find the sum of all the number of the brick that lies exactly in middle. For the above case the bricks which lies exactly in the middle are 3,11 and 15 therefore the sum is 29.

Input format

First line of input contains the number of test cases. Followed by T lines containing the Height of pyramid corresponding to each test case.

Output format

Output contains T lines containing the required sum corresponding to each test case.