OVER - Sir and The Super Over Tale

no tags 

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

hide comments
nadstratosfer: 2018-07-21 18:41:29

Handle blanklines in input when solving with Python else NZEC.

Unnati Gupta: 2014-08-07 12:35:05

make sure you use unsigned long long int.
costed me to WA

Alexandre Henrique Afonso Campos: 2014-02-02 00:52:56

I think that there are more \n in the input than specified. It may not do any difference in C, but it does make difference in other languages like Python.

rishabhshinghal: 2014-01-24 15:17:01

sort of making dp(1-D)
after solving this try M3TILE

rajat singh: 2014-01-21 12:56:51

What is the o/p for N=1

Last edit: 2014-01-21 17:35:55
lokesh gopu: 2013-12-15 08:38:41

easy :P

[Lakshman]: 2013-11-26 06:59:12

@ Reena Verma He can score as following
2,4
4,2
6,4
4,6
2,2
4,4
6,6

Reena Verma: 2013-11-18 14:21:13

anyone please tell me how the 7 comes for 2 balls

Aswin Murugesh: 2013-11-08 20:16:56

@Javed: There is something wrong with the input file. May be some extra line or something. Same method gives NZEC in python but AC in c. jus check it out..


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