Задача G. Три богатыря ≡

Условие

Три богатыря бьются со Змеем Горынычем. Илья Муромец каждым своим ударом отрубает Змею половину всех голов и еще одну, Добрыня Никитич — треть всех голов и еще одну, Алеша Попович — четверть всех голов и еще одну. Богатыри бьют по одному в каком хотят порядке, отрубая каждым ударом целое число голов. Если ни один богатырь не может ударить (число голов получается нецелым), Змей съедает всех троих. Смогут ли богатыри отрубить все головы Змею? Какое минимальное количество ударов им понадобится?

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

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

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

Выведите одно натуральное число — минимальное количество ударов, необходимое богатырям для победы. Если же победит Змей Горыныч, выведите число -1.

Ограничения

1 ≤ n ≤ 10⁵

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

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

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

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

В примере у Змея 10 голов. Первый удар наносит Илья Муромец и отрубает 5 + 1 голову. Второй удар наносит Алеша Попович и отрубает у четырехглавого змея 1 + 1 голову. Последний удар наносит Илья Муромец и отрубает у двуглавого змея 1 + 1 голову. Всего потребовалось три удара.

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

10

3