raju-hates-oddity-2

Raju has recently learnt converting a binary string into a decimal number. Raju likes this base conversion very much but he doesn't like binary strings that contain substrings having odd number of contiguous 1's. Help Raju to find the total number of decimal numbers that can be generated from a binary string of length L that does not contain substrings having odd number of contiguous 1's.
Input
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
 Each test case contains a single line denoting the length L of the binary string.

Output

Output contains T lines, each line denoting the number of all possible binary strings of respective length.

Constraints
 1 ≤ T ≤ 1000
 1 ≤ L ≤ 40

SAMPLE INPUT
2
1
2

SAMPLE OUTPUT
1
2

Explanation

Example case 1. Only one decimal number {0} is possible having binary equivalent '0'.
Example case 2. Two decimals {0, 3} having binary equivalents {'00','11'} respectively are possible.

Source: hackerearth | Difficulty: UNKNOWN_DIFFICULTY


Solutions: