Uncle Scrooge manufactured many gold bars and numbered them with sequences of zeros and ones of length 2N-2 (each bar's number is stamped on it). It is known that

1. Any two bars have different numbers.
2. The number of any bar does not contain two successive zeros.
3. For any sequence with property 2, there is a bar with this number in Uncle Scrooge's collection.

Then Uncle Scrooge decided to put his gold bars to safes. The codes for the safes are selected similarly to the numbers of the bars. Namely,

1. A code for a safe is a sequence of zeros and ones of length N-2.
2. Codes for any two safes are different.
3. The code for any safe does not contain two successive zeros.
4. For any code with properties 1 and 3, there is a safe with this number in Uncle Scrooge's depository.

Uncle Scrooge put in each of the safes the same number of gold bars. As for the remaining bars (there are less of them than the safes), he decided to give them for charity. You should find the number of gold bars in each of Uncle Scrooge's safes.

The integer 3 ≤ N ≤ 70000.

Output the number of bars in each of the safes.