Математична задача
Обмеження: 2 сек., 256 МіБ
Під час підготовки до ЗНО з математики, Марічка натрапила на цікаву задачу. У задачі просять перетворити ціле додатнє число n у число 1 за мінімальну кількість операцій або визначити що його взагалі не можна перетворити у 1. За одну операцію можна поділити число на 4, якщо число ділиться націло на 4, або відняти від числа 7, якщо результат вийде більшим ніж 0.
Марічка не змогла впоратись з цією задачею, тому попросила Зеника про допомогу. Зеник одразу звернувся до Вас, знаючи, що таким програмістам як Ви, розв’язання цієї задачі не складе труднощів.
Вхідні дані
У єдиному рядку задано єдине число — n.
Вихідні дані
Виведіть одне число — мінімальну кількість операцій, яка потрібна для того, щоб перетворити n у одиницю, або -1, якщо n взагалі не можна перетворити у 1.
Обмеження
50% тестів: 1≤n≤105.
50% тестів: 1≤n≤109.
Приклади
| Вхідні дані (stdin) | Вихідні дані (stdout) |
|---|---|
| 11 | 2 |
| Вхідні дані (stdin) | Вихідні дані (stdout) |
|---|---|
| 9 | -1 |
Примітки
Від 11 можна відняти 7, а потім поділити результат на 4, щоб одержати 1.