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
DaRksTar: 2012-07-04 14:31:31

good ques \m/

REPLY : Thanks :) :)

Last edit: 2012-09-02 11:47:28
greenland: 2012-07-03 21:52:21

plz read the output statement very carefully...
costed me 2 WAs..

Nitin Sharma: 2012-07-03 19:28:26

Erlang to the rescue :)

MR. BEAN : 2012-06-21 06:53:49

is ans for n=8 , 67 ???

PANKAJ SAINI: 2012-06-14 05:20:00

it is clear here,
i means if 3 is followed then only be followed by 1 or 5.
i.e
either 31 or 35 is possible, 33 and 37 is not possible

Abhishek Mishra: 2012-06-14 05:08:15

for 2 ans 6 is only possible if there is or instead of and in your question
then the possible combinations are
13,31,35,57,75,73

Abhishek Mishra: 2012-06-14 05:05:13

language of question is not clear 3 is followed by 1 and 5 means 31 is not valid?
as for 3 only 315 played the role...?

PubLic_AvenGeR: 2012-05-26 08:06:53

10 lines of python code will do once u get the logic...nice ques :)

srikanth reddy: 2012-04-17 15:16:44

Easy but Nice Prob :)
do check for the case N = 0!!

Devil D: 2012-04-17 15:16:44

Got AC at last with .20 seconds :)

Last edit: 2012-04-13 06:33:05

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