수 만들기

처음 수는 1이다. 세 가지 연산을 원하는 순서로 사용해서 수 N을 만들려고 한다. 가능한 연산은 다음과 같다.

1. 현재 수에 1을 더한다.
2. 현재 수가 1보다 크면 현재 수에서 1을 뺀다.
3. 자연수 x를 하나 골라 현재 수를 현재 수^x로 바꾼다.

N을 만들기 위해 필요한 연산 횟수의 최솟값을 구하라.

첫째 줄에 자연수 N이 주어진다. N은 10^18 이하이다.

첫째 줄에 필요한 최소 연산 횟수를 출력한다.