### Problem Statement

There is nothing more beautiful than just an integer number.

You start with the integer 1 and you apply a sequence of operations until you reach the integer n. Each operation can be one of the following:

• Increment the current number by 1.
• If the current number is greater than 1, decrement it by 1.
• Raise the current number to any positive integral power.

Return the minimum possible number of operations required to reach n.

### Definition

 Class: ThePower Method: count Parameters: long Returns: int Method signature: int count(long n) (be sure your method is public)

### Constraints

-n will be between 1 and 10^18, inclusive.

### Examples

0)

 `8`
`Returns: 2`
 1. Increment by 1: 1 + 1 = 2. 2. Raise to the power of 3: 2^3 = 8.
1)

 `1`
`Returns: 0`
 We don't need any operations here.
2)

 `80`
`Returns: 4`
 1. Increment by 1: 1 + 1 = 2. 2. Increment by 1: 2 + 1 = 3. 3. Raise to the power of 4: 3^4 = 81. 4. Decrement by 1: 81 - 1 = 80.
3)

 `123456789`
`Returns: 2566`

#### Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=10235

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=13699&pm=10235

Vasyl[alphacom]

#### Testers:

PabloGilberto , bmerry , ivan_metelsky

Search