PGR01 - Progressions

no tags 

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

hide comments
noble_mushtak: 2019-06-28 03:27:04

Very easy to solve using OEIS!

aditya_rev: 2016-09-08 07:06:03

ez.. first go :)

DIWAKAR BHARDWAJ: 2015-01-14 11:39:58

easy but tricky got ac at 1st attempt

Raj Kumar Chauhan: 2014-08-07 12:57:44

can anyone tell me how to get solution of questions?

pandu ranga rao: 2014-07-27 11:04:57

Sir @Bala Sai Charan can u please provide submit link for the above problem.... Thanq

Last edit: 2014-07-27 13:19:34

Added by:Bala sai charan
Date:2014-07-27
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Simple Math