NUMPLAY - Fun with numbers

no tags 

Consider a set of 4 numbers {1, 3, 5, 7}. Form a number using these digits in the set under the following constraints,1 can be followed only by 3 (i.e. the number may contain 13 but not 15 or 17 or 11 eg:13573 is valid but not 113573), 3 can be followed only by 1 and 5, 5 can be followed only by 7, 7 can be followed only by 5 and 3.

Find the number of such numbers of length n.

e.g.: 37, 51, 53, 71 are all not a valid number of length 2. 131 is a valid number of length 3. 1357 and 1313 are all a valid number of length 4 but 11 or 1537 or 15 or 17 or 33 are not valid numbers.

Input

t, First line of input contains number of test cases 0 <= t <= 40.

Remaining t lines consist of length n for each test case 0 <= n <= 10000.

Output

Output the number of possible numbers of length n followed by a line (note long long int in C++ may not be sufficient.)

Example

Input:
3
2
1
4

Output:
6
4
13

Note: time limit is reduced for checking the accuracy.


hide comments
Ivan Hendrajaya: 2012-04-17 15:16:44

@B.R.ARVIND: Thanks, just follow my intuition. :)

B.R.ARVIND: 2012-04-17 15:16:44

@Ivan Hendrajaya:superb solution :)

(Tjandra Satria Gunawan)(曾毅昆): 2012-04-17 15:16:44

nice problem ;)

noname: 2012-04-17 15:16:44

some more test cases please...

B.R.ARVIND: 2012-04-17 15:16:44

@numerix: in such a case ,i have to rejudge everyone's solutions .

numerix: 2012-04-17 15:16:44

@problemsetter: Thanks for answering and explanation. But why did you delete my comment? As you refer to that comment, it would have been better not to remove it.
And let me repeat my suggestion to reduce timelimit e.g. to 1 s to avoid solutions that are (very) far away from optimal (according to the runtime).

B.R.ARVIND: 2012-04-17 15:16:44

@confused:dont get confused:P .look at the question, 37,51,53,71 are all NOT a valid number

B.R.ARVIND: 2012-04-17 15:16:44

problem with all changes made

B.R.ARVIND: 2012-04-17 15:16:44

@numerix:this changes were made because this is my first problem.no more such changes ll be made in future @santhana:how can there be a number of length 0 ?

Santhana Krishnan: 2012-04-17 15:16:44

The test cases are expecting 0 as output for n=0. Should be 1 in my opinion.


Added by:B.R.ARVIND
Date:2012-04-03
Time limit:1s
Source limit:30000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:own problem