Magic Tree Growth

This problem involves calculating the height of a Magic Tree after a given number of time units. The tree grows in a unique manner: starting with an initial height of 1, its height is updated in each time unit by alternating multiplications. Specifically, at each time unit i (starting from 1), if i is odd then the height is multiplied by 3, and if i is even then the height is multiplied by 2.

The growth process can be described by the following recurrence with an initial condition:

\( H(0)=1 \)

For each time unit i (with i \ge 1):

• If \( i \) is odd: \( H(i)=H(i-1)\times3 \).
• If \( i \) is even: \( H(i)=H(i-1)\times2 \).

Your task is to compute the height of the Magic Tree for a list of given time units.

For example, when \( n=0 \), the height is 1; for \( n=1 \), the height is 3; for \( n=4 \), the height is 36.

inputFormat

The first line of input contains a single integer \( T \) representing the number of observations. Each of the following \( T \) lines contains one integer \( n \) (\( 0 \le n \le 10^6 \)), representing the time unit at which you need to compute the height of the Magic Tree.

outputFormat

For each observation, output the corresponding height of the Magic Tree on a separate line.

## sample

1
0

1

</p>