Tomorrow is the Calculus exam and you are playing with squares and dominoes.

Your room-mate shouts at you: "Chief, are you not bothered?"

You : "I am already prepared. Now, let me focus on the game."

Out of curiosity, your room-mate starts looking at the game and throws you a challenge. How many ways can you tile a board of length n using only dominoes and/or squares?

(In the above figure, the the yellow-colored rectangle indicates the board of length 3. The blue rectangle is a unit square and the green rectangle is a domino.)

Show your room-mate that you are the Chief by writing a program that can calculate the number of tilings of a n-board using only squares and dominoes.

Input

The input starts with an integer t (1 <= t <= 10^5), the number of test cases. t lines follow. Each line contains an integer value n.

Output

Corresponding to each test case, print an integer y, which is the number of ways one can tile a board of length n using squares and dominoes. It is safe to assume that y will fit into a 64-bit integer.

Example

Input: 
3
1
3
13

Output:
1
3
377

Explanation for Case 1: Only possible arrangement: s (s: square)
Explanation for Case 2: These are the three possible arrangements: s+s+s [no dominoes, only squares], s+d, d+s (s: square, d: domino).