MAIN113 - Special String

no tags 

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: 2018-12-29 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: 2017-12-19 14:37:01

use long long !

more_practice: 2016-06-27 22:50:53

attention:-it's by dp not maths

Neha Jawalkar: 2016-05-05 18:18:55

Nice one. :)

SHRINIKET ACHARYA: 2015-06-04 19:43:34

anyone did it using a general formula or can be done by dp only...?? more testcase please...

Anmol Pandey: 2014-10-24 13:13:22

Nice dp <3

Diksha Jaiswal: 2014-10-21 08:54:59

gud prblm :)

mayank: 2014-10-03 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: 2014-04-16 11:04:09

Nice problem.. 150th :)

paras meena: 2013-12-05 12:28:24

Why Math... :(


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