Devil's Sequence

The devil's sequence $x$ is defined as follows.

$x_0 = 0, \qquad x_1 = 1, \qquad x_n = \frac{x_{n-1} + x_{n-2}}{2} \quad (n \ge 2)$

For example, $x_{10} = 0.666015625$, and three sixes run from the first digit after the decimal point.

Given $n$, write a program that finds how many sixes run consecutively from the first digit after the decimal point of $x_n$.

The first line contains an integer $n$. ($2 \le n \le 100000$)

Print the number of consecutive sixes starting at the first digit after the decimal point of $x_n$. Print 0 if that digit is not a six.