곱셈기

디지털 회로 설계에서 계산 알고리즘은 연산 블록으로 구현된다. 연산 블록은 입력이 하나 이상이고 출력은 하나다. 블록 종류마다 수행하는 수학 연산이 다르다. 입력과 출력의 값은 모두 정수다. 출력값은 블록 종류와 입력값으로 정해진다.

복잡한 연산은 더 단순한 연산의 블록을 조합해 만드는 경우가 많다. 이때 각 블록의 입력은 다른 블록의 출력이나 회로의 입력 중 하나에서 값을 받아야 한다. 회로에 순환 의존성은 허용되지 않는다. 블록의 입력값이 직접 또는 간접적으로 그 블록의 출력값에 의존할 수 없다. 한 블록의 출력은 여러 블록의 입력으로 연결될 수 있다. 회로에 있는 블록 중 하나의 출력이 회로 전체의 출력으로 지정된다.

이 문제에서는 정수 $N$을 곱하는 회로를 만든다. 회로의 입력은 하나이며 값은 $x$다. 회로의 출력은 $N \cdot x$와 같아야 한다. 사용할 수 있는 블록은 다음과 같다.

1. 덧셈 블록: 입력이 두 개다. 출력은 첫 번째 입력과 두 번째 입력의 합이다.
2. 뺄셈 블록: 입력이 두 개다. 출력은 첫 번째 입력에서 두 번째 입력을 뺀 값이다.
3. $k$ 시프트 블록: 입력이 하나다. 출력은 입력값에 $2^k$를 곱한 값이다.

시프트 블록의 입력값을 덧셈 블록이나 뺄셈 블록에서 받는 것은 금지된다.

N배 곱셈 회로를 만드는 데 필요한 블록 수의 최솟값을 구하라.

첫 줄에 곱할 정수 $N$이 주어진다 ($2 \le N \le 10^3$).

곱셈 회로를 만드는 데 필요한 연산 블록 수의 최솟값을 정수 하나로 출력한다.

아래는 5개의 블록으로 140배를 만드는 회로 두 가지다. 아래쪽 회로는 시프트 블록의 입력이 덧셈 또는 뺄셈 블록에서 오므로 문제 조건에 따라 금지된 회로다.