1부터 시작해서 N을 만들려고 한다. 사용할 수 있는 연산은 아래와 같이 총 3가지이다. 이때, N을 만드는데 사용하는 연산의 최소 횟수를 구하는 프로그램을 작성하시오.</p>

1. 현재 수를 1 증가시킴 (현재 수+1)
2. 현재 수가 1보다 크면 1 감소 시킴 (현재 수-1)
3. 현재 수를 자연수 제곱함. (현재 수^x, x는 자연수)

첫째 줄에 N이 주어진다. N은 10¹⁸보다 작거나 같은 자연수이다.

출력 형식

첫째 줄에 문제의 정답을 출력한다.

예제 입력 1

80

예제 출력 1

4

예제 입력 2

8

예제 출력 2

2

예제 입력 3

1

예제 출력 3

0

예제 입력 4

123456789

예제 출력 4

2566