ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1605. Дьявольская последовательность

Ограничение времени: 0.5 секунды
Ограничение памяти: 64 МБ
Problem illustration
Рободьявол в перерывах между репетициями своего оркестра развлекается математикой. Сегодня он придумал дьявольскую последовательность № 1729:
  • x0 = 0,
  • x1 = 1,
  • xn = (xn − 1 + xn − 2) / 2.
Например, x10 = 0.666015625. Его сразу заинтересовало, со скольки шестерок начинается десятичная запись произвольного xn. Он призадумался и через 6 наносекунд вывел формулу. А вам такое под силу?

Исходные данные

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

Результат

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

Пример

исходные данныерезультат
10
3
Автор задачи: Александр Ипатов
Источник задачи: Девятое открытое личное первенство УрГУ (1 марта 2008)