cho.sh

Make a Number

Starting from 1, find the minimum number of +1, -1, and power operations needed to reach a target N up to 10^18.

Hard8Number theoryMathRecursionBacktrackingNo attempts yetTime limit2sMemory limit128 MB

Problem

The starting number is 1. You want to make the number N by applying the following three operations in any order.

  1. Add 1 to the current number.
  2. If the current number is greater than 1, subtract 1 from it.
  3. Choose a positive integer x and replace the current number with current^x.

Find the minimum number of operations needed to make N.

Input

The first line contains a positive integer N. N is at most 10^18.

Output

Print the minimum required number of operations on the first line.