Charan is good at Mathematics and he loves the concept of progressions. He was assigned a task to calculate the

n-th term in the given series. As he is good at mathematics he calculates the answer but as the series was too large he decided to write a program to solve that problem. Help Mr.Charan in solving the problem.

Given series is  t1=1,t2=9,t3=45,t4=189,t5=729.....

Here, tn=n-th term in the series. 

Input

First line represents the number of test cases.
Next t lines represent the n value. 
1<=tn<10^18 

Output

Output the corresponding value of the n-th term

Example

Input:
1
10

Output:
373977