이쑤시개 산술

이쑤시개 수식은 이쑤시개로 양의 정수를 나타낸다. 수식은 피연산자와 연산자로 이루어진다.

• 피연산자는 하나 이상의 세로 이쑤시개 |로 이루어지며, 그 값은 사용한 이쑤시개의 개수와 같다. (예를 들어 |||의 값은 3이다.)
• 연산자는 두 종류이며, 각각 정확히 이쑤시개 2개로 이루어진다.
  • 덧셈은 더하기 기호 +로, 세로 이쑤시개 하나와 가로 이쑤시개 하나로 이루어진다.
  • 곱셈은 문자 x로, 이쑤시개 2개로 이루어진다. 곱셈은 덧셈보다 우선순위가 높다.

수식은 반드시 피연산자로 시작하여 연산자와 피연산자가 번갈아 나오고, 마지막도 피연산자로 끝나야 한다. 예를 들어 |||||||x|||||의 값은 $7 \times 5 = 35$이고, 이쑤시개를 $7 + 5 + 2 = 14$개 사용한다.

양의 정수 $N$이 주어질 때, 값이 $N$인 모든 이쑤시개 수식을 생각하자. 그러한 수식이 사용할 수 있는 이쑤시개의 최소 개수를 구하여라.

입력은 한 줄 이상으로 이루어진다. 각 줄에는 양의 정수 $N$이 하나 주어지며 $1 \le N \le 5000$이다. 입력은 파일의 끝에서 종료된다.

입력의 각 정수 $N$에 대하여, 값이 $N$인 이쑤시개 수식을 만드는 데 필요한 이쑤시개의 최소 개수를 한 줄에 출력한다.