시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
0.5 초 64 MB 45 15 5 27.778%

문제

악마의 수열은 다음과 같이 정의된다.

  • x0 = 0
  • x1 = 1
  • xn = (xn-1 + xn-2) / 2

예를 들어, x10 = 0.666015625 이다. n이 주어졌을 때, xn의 첫부분에 6이 몇 개 연속되는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n (2 ≤ n ≤ 100000)이 주어진다.

출력

xn의 첫부분에 6이 몇 개 연속되는지 출력한다.

예제 입력

10

예제 출력

3

힌트

출처