Задача E. Двоичные числа с чередующимися цифрами

Автор:Антон Карабанов   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:512 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

Тимофей очень любит двоичные числа, в которых единицы и нули чередуются, например 1, 10, 101, 1010, 10101 и так далее. Все такие числа (в единственном экземпляре) он аккуратно хранит на карточках в специальном альбоме.

Сегодня Тимофей хочет представить десятичное число n в виде суммы чисел из альбома. Поскольку ему жалко расставаться со своими числами, он хочет найти наименьшее число своих карточек, числа на которых в сумме дают n. Сколько карточек понадобится Тимофею?

Формат входных данных

Единственная строка входного файла содержит одно натуральное десятичное число n.

Формат выходных данных

Выведите одно натуральное число — ответ на задачу. Если число n невозможно представить в виде суммы имеющихся чисел — выведите число -1.

Ограничения

1 ≤ n ≤ 1015

Система оценки и описание подзадач

Баллы за каждый тест начисляются независимо.

Решения, верно работающие при 1 ≤ n ≤ 100, получат не менее 40 баллов.

Решения, верно работающие при 1 ≤ n ≤ 105, получат не менее 80 баллов.

Пояснения к примерам

В первом примере число 23 можно представить в виде суммы чисел 21 (101012) и 2 (102). Всего два слагаемых.

Во втором примере нет возможности представить число 9 в виде суммы чисел из альбома.

Примеры тестов

Стандартный вход Стандартный выход
1
23
2
2
9
-1

0.112s 0.021s 15