악마의 수열

악마의 수열 $x$는 다음과 같이 정의한다.

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

예를 들어 $x_{10} = 0.666015625$이고, 소수점 아래 첫째 자리부터 6이 3개 연속된다.

$n$이 주어졌을 때, $x_n$을 소수로 적으면 소수점 아래 첫째 자리부터 6이 몇 개 연속되는지 구하는 프로그램을 작성하시오.

첫째 줄에 정수 $n$이 주어진다. ($2 \le n \le 100000$)

첫째 줄에 $x_n$의 소수점 아래 첫째 자리부터 연속되는 6의 개수를 출력한다. 첫째 자리가 6이 아니면 0을 출력한다.