I. Две операции
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Ваша учительница по математике Агриппина Сергеевна написала на доске число $$$1$$$. Задача класса на сегодняшний урок — получить из него число $$$N$$$. Разумеется, ваши действия ограничены определенным набором возможных операций. Все, что вы можете сделать — это

  • удвоить написанное на доске число число;
  • переставить цифры числа в произвольном порядке (при этом новое число не должно начинаться с нуля).

Всем хочется поскорее пойти домой, поэтому было бы приятно получить число $$$N$$$ за минимальное число операций. Помогите классу (и себе), и найдите какое минимальное число описанных операций требуется потратить, чтобы получить число $$$N$$$, или определите, что это невозможно, и тогда всем придется сидеть до конца урока.

Входные данные

Единственная строка ввода содержит целое число $$$N$$$, которое нужно получить ($$$1 \leqslant N \leqslant 9999$$$).

Выходные данные

Выведите одно целое число — наименьшее количество операций, за которое можно получить $$$N$$$, или «-1», если это невозможно.

Примеры
Входные данные
4
Выходные данные
2
Входные данные
61
Выходные данные
5
Входные данные
3
Выходные данные
-1
Примечание

В первом примере сработает такая последовательность действий: $$$1 \to 2 \to 4$$$.

Во втором примере можно действовать так: $$$1 \to 2 \to 4 \to 8 \to 16 \to 61$$$.