문제1566--ForbiddenStrings

### 1566: ForbiddenStrings

실행시간 제한: 1 Sec  메모리사용 제한: 128 MB
제출: 114  통과: 58
[제출] [채점기록] [묻고답하기]

#### 문제 설명

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.

#### 입력 예시 Copy

3
2
3
4


#### 출력 예시 Copy

9
21
51