AMZRCK - Amz Rock

no tags 

To many people in many cultures, music is an important part of their way of life.

AmzMohammad is a fan of rock music. and he have n rock tracks (labled from 1 to n) now he wanna select a playlist.

in his opinion a good playlist is one that have no two successive tracks.

in how many ways?

Input

first line = number of test cases

each testcase in an integer n(number of tracks)

Output

Output number of good playlists he can make.

answer is less than 1000000000. it is the only constraint :)

Example

Input:
2
1
2

Output:
2
3
note: a good play list may consist 0 track :)
note 2: how many persian rock tracks we have?

hide comments
sonuverma: 2018-01-09 11:50:35

"in his opinion a good playlist is one that have no two successive tracks."
*concecutive
not successive. :-)

sanyam19: 2018-01-08 13:06:09

easy 1 :)
try to observe d pattern

nikhil2504: 2017-07-27 18:15:09

dp <3

aexpo: 2017-07-27 17:50:25

The tracks in the play list should be in an ascending order only.Do not rearrange them.
The question is a bit unclear though.

srnsh: 2017-01-31 17:16:52

Beware :: Spoilers in Comments --__--

surajmall: 2016-10-12 06:09:03

real time fabonnici use

ranjeetkumar: 2016-06-30 20:09:03

too much spoilers in comment

kolahzary: 2016-03-13 01:17:21

Wrote it in C# but C# is not acceptable for this problem :((
I wonder why !

manas0008: 2016-01-29 05:10:33

got WA when used a direct formula.But AC with a simple precomputation.Just watch first 4,5 consecutive testcases you'll get it.

Shashank Tiwari: 2015-12-12 19:03:07

Question is bit unclear .

Well , Question can be restated as : Given 'n' , we have a set of numbers {1,2,3 ,..... ,n} . we need to find count of all possible subsets of it such that no 2 consecutive number appears in any of the subsets. Empty set is allowed.

ex : if n=3 , we have {1,2,3}. Possible sets are {} , {1}, {2} ,{3} ,{1,3}. Hence count = 5. Note that {1,2} or {2,3} are not allowed as they are consecutive.

Also, It comes out that 1<=n <= 42 for this question.

Last edit: 2015-12-12 19:40:54

Added by:mohammad mahmoodi
Date:2012-08-01
Time limit:0.100s-0.150s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GAWK BASH CSHARP GO ICON ICK WHITESPACE
Resource:AmzMohammad ( Mohammad Mahmoodi )