TILEGAME - Tile game
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).
Added by: | Siddharth Kothari |
Date: | 2010-09-27 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | Own problem |