Make a Number

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.

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

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