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

Условие

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

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

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

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

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

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

Ограничения

1 ≤ n ≤ 10¹⁵

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

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

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

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

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

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

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

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

23

2

9

-1