문제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

출처/분류