Under construction

Still being built. Things may change

Make a Number

Time limit2sMemory limit128 MB

Summary

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

Level: Hard8 of 10
Topics: Number theory, Math, Recursion, Backtracking
Solved: No attempts yet

Problem

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

Add 1 to the current number.
If the current number is greater than 1, subtract 1 from it.
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.

Examples4

Example 1
Input
```
80
```
Expected output
```
4
```
Example 2
Input
```
8
```
Expected output
```
2
```
Example 3
Input
```
1
```
Expected output
```
0
```
Example 4
Input
```
123456789
```
Expected output
```
2566
```

Loading...