You make a visit to an uninhabited island with a new pair of species, let's call them POPO! Each pair of POPO (one male and one female) who mature at the age of one month, have two offspring (one male and one female) each month after that, and live forever. The speciality of the species is that each pair of POPO, mature in one month and then produce a pair of new-borns at the beginning of every following month. How many pairs of POPO will there be after n months?

Input

1. Line 1 contains number of test cases.

2. The following lines contain the values of n. (0 <= n <= 90)

Output

The number of pairs of species for corresponding values of n.

Input:
1
0

Output:
1