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 is the number of test cases.

Each test case 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?