#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