Uncle Scrooge made a lot of gold bars and numbered them with sequences of zeros and ones of length 2n - 2 (the number of each ingot is stamped on it). It is known that

1. Any two ingots have different numbers.
2. In the number of any ingot there is no two zeros in a row.
3. For any sequence corresponding to the property 2, there is an ingot with such number in the Uncle Scrooge's collection.

Then Uncle Scrooge decided to put the bars into safes. Codes for safes are matched in a similar way to numbers of ingots. Namely

1. The code to the safe is a sequence of zeros and ones of length n - 2.
2. The codes for any two safes are different.
3. There is no any safe with a code that contains two zeros in a row.
4. For any code that corresponds to the properties 1 and 3, the safe with this code is in the Uncle Scrooge's store.

Uncle Scrooge put in each safe the same number of gold bars, and the remaining ingots (they were left less than safes) decided to send to charity. Find how many ingots are in each of the safes of Uncle Scrooge.

Input

One integer n (3 ≤ n ≤ 70000).

Output

Print the number of gold bars in each safe.