Unique Terrain Paths

In this problem, you are given a path divided into V sections. Each section can be assigned one of three terrain types: flat, uphill, or downhill. However, two consecutive sections cannot be assigned the same type. Your task is to compute the number of valid assignments for the V sections.

It can be observed that for one section (V = 1) there are 3 possible assignments. For V ≥ 2, once the first section is assigned a terrain (3 choices), every subsequent section has 2 choices (any type different from the previous one). Hence, the answer can be computed using the formula:

( 3 \times 2^{V-1} )

This problem tests your ability to work with simple recurrence relations and manage large numbers when V is large.

inputFormat

The input is read from standard input (stdin).

The first line contains an integer T, the number of test cases. Each of the following T lines contains a single integer V, representing the number of sections.

outputFormat

For each test case, output the number of valid terrain assignments on a separate line to standard output (stdout).## sample

1
1

3