Математична задача

Обмеження: 2 сек., 256 МіБ

Під час підготовки до ЗНО з математики, Марічка натрапила на цікаву задачу. У задачі просять перетворити ціле додатнє число \(n\) у число 1 за мінімальну кількість операцій або визначити що його взагалі не можна перетворити у 1. За одну операцію можна поділити число на 4, якщо число ділиться націло на 4, або відняти від числа 7, якщо результат вийде більшим ніж 0.

Марічка не змогла впоратись з цією задачею, тому попросила Зеника про допомогу. Зеник одразу звернувся до Вас, знаючи, що таким програмістам як Ви, розв’язання цієї задачі не складе труднощів.

Вхідні дані

У єдиному рядку задано єдине число — \(n\).

Вихідні дані

Виведіть одне число — мінімальну кількість операцій, яка потрібна для того, щоб перетворити \(n\) у одиницю, або -1, якщо \(n\) взагалі не можна перетворити у 1.

Обмеження

\(50\%\) тестів: \(1 \le n \le 10^5\).

\(50\%\) тестів: \(1 \le n \le 10^9\).

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
11	2

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
9	-1

Примітки

Від 11 можна відняти 7, а потім поділити результат на 4, щоб одержати 1.