Abhishek is very fond of series and he loves solving them. He thinks that no one can match his skills at series and so he throws a challenge at you.

The challenge is to determine the sum of the first N terms of the series.

The series is as: 0 1 2 6 20 56 144 352....
Be careful while finding the Nth term, it is not always determined by the starting terms ;)

Input

The first Line of input contains number of test cases T (<= 100), then T lines follow.
For each test case there will be a number N (<= 30).

Output

Output the sum of series until N terms

Example

Input:
2
2
5

Output:
1
29