OVER - Sir and The Super Over Tale

After a terrible start against MI, CSK had managed a reasonable total from their 20 overs. Now it was the turn of the bowling department, and they did their best by keeping MI at the same score. The match is tied and a Super Over is due. Who could it be for CSK other than ‘The Sir’ himself? So Sir Jadeja has got the responsibility to bring CSK home. But Sir has a strange way of scoring runs. He scores runs only in 2s, 4s, and 6s (that’s why we call him Sir :p). He wonders if there were N balls to face, in how many ways he can score runs such that the difference of number of runs scored on consecutive balls is at max two. Help Sir to solve the mystery and make the bowlers feel some hard time on the field.

Input

First line contains an integer T, the number of test cases. T lines follow,  each containing an integer N, 1 <= N <= 50.

Output

An integer which is the required answer.

Example

Input:
2
2
3

Output: 7
17

Added by:Aaquib Javed
Date:2013-10-03
Time limit:0.100s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own Problem used in LiveWire 2k13, NIT Allahabad

hide comments
2013-10-25 16:17:24 numerix
@Lakshman: If I remember right, there had been a comment here about some trouble with the input. So I did not try standard reading, but used some kind of "bullet-proof"-reading and got AC with my first and only submission.
2013-10-25 16:12:03 [Lakshman]
Okay numerix , Finally done. But don't know why I am getting runtime error with python on 3rd test case.
@Aaquib Javed can you please check My python code.
Thanks.
2013-10-25 12:40:50 numerix
@Lakshman: The example must be enough. Any further i/o-pair would give too much away and makes it too easy to look it up somewhere. If you simulate the process (less than 10 lines of Python code) you will find out yourself.
2013-10-25 07:51:20 [Lakshman]
what is ans for 5.?
2013-10-23 10:06:51 dmaniac
a simple problem, just look at the series formed :)
2013-10-20 16:30:08 Atul Kumar Verma
my solution using unsigned long long does not work for n = 50 still AC.
2013-10-19 11:47:46 anurag garg
piece of cake....:-)
my 100th on spoj
2013-10-18 19:45:31 CoNtRaDiCtIoN
C users use unsigned long long int
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.