55 1 s 128 MB

A string of letters A, B, C is forbidden if there are three consecutive letters from which one is A, one is B, and one is C. For example, BAACAACCBAAA is forbidden, while AABBCCAABB is not.

The first line of the input gives a number of test cases, T (1 <= T <= 30).

Each case is consists of an integer n. n will be between 1 and 30, inclusive.

For each test case, print the how many such strings of length n are not forbidden. Answer can larger than 2^32.

## Sample Input | ## Sample Output |
---|---|

3 2 3 4 | 9 21 51 |