ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

1605. Devil's Sequence

Time limit: 0.5 second
Memory limit: 64 MB
Problem illustration
Robodevil likes to do some mathematics between rehearsals of his orchestra. Today he invented devilish sequence No. 1729:
  • x0 = 0,
  • x1 = 1,
  • xn = (xn − 1 + xn − 2) / 2.
For example, x10 = 0.666015625. Robodevil became interested at once how many sixes there were at the beginning of an arbitrary xn. 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 xn in decimal notation.

Sample

inputoutput
10
3
Problem Author: Alexander Ipatov
Problem Source: IX USU Open Personal Contest (March 1, 2008)