거듭제곱 최소 연산

1 <= P <= 20,000인 P에 대해 x^P를 가능한 한 적은 연산으로 계산하려고 한다. 계산 중에는 두 개의 변수만 사용할 수 있다.

처음에는 한 변수에 x, 다른 변수에 1이 저장되어 있다. 한 번의 연산에서는 현재 두 변수에 저장된 값 중 두 값을 골라 곱하거나, 한 값을 다른 값으로 나눈 결과를 두 변수 중 하나에 저장한다. 같은 변수를 두 번 골라 제곱할 수도 있다. 최종 결과는 어느 변수에 저장되어도 상관없다.

예를 들어 x^9는 다음과 같이 4번의 연산으로 계산할 수 있다.

P가 주어졌을 때, x^P를 계산하는 데 필요한 최소 연산 횟수를 구하라.

첫째 줄에 P가 주어진다.

최소 연산 횟수를 출력한다.