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
paras meena: 2013-12-05 12:28:24

Why Math... :(

SYNTAX TERROR: 2013-10-20 20:25:18

Please give some more test cases.. problem is not clear.. In case of strings be a little more descriptive

samuel: 2013-07-05 02:30:33

nice problem!
simple mathematic

Parshant garg: 2013-05-14 09:45:05

is xyzx or xyyyyxyz is special?
xyz can be in any order?
or is whole string consist of xyz?
give more test cases?

moustafa maher: 2013-04-25 06:20:05

@admin...plz post back the comment of akuya :D :D

RAMAKRISHNAN.K: 2013-03-29 06:37:30

More testcases please..

The Mundane Programmer: 2013-03-14 03:43:44

GOT AC , just easy one.....

Last edit: 2013-03-14 03:46:00
Sardar Khan: 2012-09-01 19:41:45

@akuya: thnkx ur comment helped!!:)

BOND: 2012-08-18 09:54:05

I had to comment on this, it took nearly 3 hrs, and now feeling relieved after seeing that green bar...


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