## #1566 ForbiddenStrings

55  1 s   128 MB

## Description

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.

## Input

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.

## Output

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

### Sample Output

3
2
3
4

9
21
51