Crystal (Unknown)

The precious stone Anknown has a unique crystal lattice that allows it to be split into either eight or twelve pieces in a single break. For jewelry crafting, you need exactly N parts. Determine the minimum number of breaks required to achieve this from a single crystal.

Input

The input consists of a single integer N (1 ≤ N ≤ 1,000,000), representing the number of parts needed.

Output

Output the minimum number of breaks required. If it is impossible to obtain exactly N parts, output -1.

Examples