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 (labelled from 1 to n) now he wants to 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?