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
nadstratosfer:
20181229 23:57:33
Annoyingly bad statement! Consider a set of strings of length n, made only of letters "x", "y" and "z". Compute number of such strings that don't contain a substring of size 3, in which each letter is different (eg. any substring that is a permutation of "xyz"). For example, s = yzxzx is a special string because len(set(s[0:3])) = 3. 

amulyagaur:
20171219 14:37:01
use long long ! 

more_practice:
20160627 22:50:53
attention:it's by dp not maths 

Neha Jawalkar:
20160505 18:18:55
Nice one. :) 

SHRINIKET ACHARYA:
20150604 19:43:34
anyone did it using a general formula or can be done by dp only...?? more testcase please...


Anmol Pandey:
20141024 13:13:22
Nice dp <3 

Diksha Jaiswal:
20141021 08:54:59
gud prblm :) 

mayank:
20141003 14:46:03
Did by DP :) . Unnecessary confusion can be avoided by adding "any" in place of blank in the statement "there is ___ three consecutive letters ", ie xxyz is a special string. Hope this helps. 

AlcatraZ:
20140416 11:04:09
Nice problem.. 150th :) 

paras meena:
20131205 12:28:24
Why Math... :(

Added by:  amit karmakar 
Date:  20110815 
Time limit:  0.281s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 