Robodevil likes to do some mathematics between rehearsals of his orchestra.
Today he invented devilish sequence No. 1729:

*x*_{0} = 0,
*x*_{1} = 1,
*x*_{n} = (*x*_{n − 1} + *x*_{n − 2}) / 2.

For example,

*x*_{10} = 0.666015625. Robodevil became interested
at once how many sixes there were at the beginning of an arbitrary

*x*_{n}.
In 6 nanoseconds, he had a formula. Can you do the same?

### Input

You are given an integer *n*; 2 ≤ *n* ≤ 100000.

### Output

Output the number of sixes at the beginning of *x*_{n} in decimal notation.

### Sample

**Problem Author: **Alexander Ipatov

**Problem Source: **IX USU Open Personal Contest (March 1, 2008)