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

Limits: 2 sec., 256 MiB

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

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

Input

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

Output

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

Constraints

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

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

Samples

Input (stdin) сopy	Output (stdout) сopy
11	2

Input (stdin) сopy	Output (stdout) сopy
9	-1

Notes

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