Mathematical Problem

Limits: 2 sec., 256 MiB

This statement was translated automatically from Ukrainian.

While preparing for the math ZNO, Marichka came across an interesting problem. The problem asks to convert a positive integer \(n\) into the number 1 using the minimum number of operations, or to determine that it cannot be converted to 1 at all. In one operation, you can either divide the number by 4 if it is evenly divisible by 4, or subtract 7 from the number if the result is greater than 0.

Marichka could not handle this problem, so she asked Zenik for help. Zenik immediately turned to you, knowing that for programmers like you, solving this problem will not be difficult.

Input

The single line contains a single number — \(n\).

Output

Print a single number — the minimum number of operations required to convert \(n\) into one, or -1 if \(n\) cannot be converted to 1 at all.

Constraints

\(50\%\) of tests: \(1 \le n \le 10^5\).

\(50\%\) of tests: \(1 \le n \le 10^9\).

Samples

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

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

Notes

From 11 you can subtract 7, and then divide the result by 4 to get 1.