Wolfgang Puck has two very peculiar habits:
One day Wolfgang wondered in how many different ways he can pack his cakes into certain sized boxes. Can you help him?
The precise sizes of the cakes Wolfgang makes and one way to pack them in a box of length 6.
The five ways to pack a box of length 2.
The input begins with t, the number of different box lengths. The following t lines contain an integer n (1 ≤ n ≤ 40).
For each n output on a separate line the number of different ways to pack a 2-by-n box with cakes described above. Output is guaranteed to be less than 1018.
2 1 2
1 5