Рободьявол в перерывах между репетициями своего оркестра развлекается математикой. Сегодня он придумал дьявольскую последовательность № 1729:

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

Например, x₁₀ = 0.666015625. Его сразу заинтересовало, со скольки шестерок начинается десятичная запись произвольного x_n. Он призадумался и через 6 наносекунд вывел формулу. А вам такое под силу?

В единственной строке записано целое число n (2 ≤ n ≤ 100000).

Выведите целое число — количество шестерок, с которых начинается десятичная запись x_n.