MAIN113  Special String
A string of letters X, Y, Z is special if there are three consecutive letters from which one is X, one is Y, and one is Z. For example, XYZXYZ is special, while XXYYZ is not. Your task is to calculate how many such strings of length n are not special.
Input
First line contains an integer T(1 <= T <= 30) which denotes the total number of test cases. Each test case contains an integer N(1 <= N <= 30) in a single line.
Output
For each test case print total number of strings which have a length N and are not special.
Example
Input:
1
2
Output:
9
hide comments
Zhiang:
20120817 17:41:18
@admin..plz remove the comment of akuya


Rajesh Kumar:
20111113 22:15:23
More test cases please... 

Gaurav Mittal:
20110921 16:59:16
is xxyz special? 

Gunjit :
20110920 09:37:05
plz give sm more test cases...


Rachmawan Atmaji Perdana:
20110904 12:42:44
Integer is not enough 

Alex Anderson:
20110825 16:45:23
Why is N limited to 30? 

Akshat Aggarwal:
20110825 02:51:13
Last edit: 20110825 08:11:35 

Gregorius Edward:
20110824 03:02:44
do xxyz and xyzx are special? 
Added by:  amit karmakar 
Date:  20110815 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 