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

• x₀ = 0,
• x₁ = 1,
• x_n = (x_{n − 1} + x_{n − 2}) / 2.

For example, x₁₀ = 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?

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

Output the number of sixes at the beginning of x_n in decimal notation.