RANJAN02 - Tower Of Hanoi - Revisited

Given 3 three pegs: leftmost peg A, middle peg B and rightmost peg C. Find the shortest sequence of moves that transfers a tower of n disks from the left peg A to the right peg C, if direct moves between A and C are disallowed. (Each move must be to or from the middle peg B.)

Constraints

  • Initially the left peg A in stacked by n disks in the order of decreasing size.
  • Only one move can be done at a time and never moving a larger one onto a smaller.
  • Number of moves will always be less than 2^64.
  • 1 <= n <= 35

Input

Input begins with an integer t, followed by t lines. Each line has the number of disks n.

Output

For each test case, output the minimum number of move required to transfer the n disks from peg A to peg C.

Example

Input:
4
1
2
5
10

Output:
2
8
242
59048

Added by:abhiranjan
Date:2010-09-28
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:IIITM Local Contest

hide comments
2013-01-23 16:08:29 abhiranjan
@~ - Constraint 3 may help you.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.