Toothpick Arithmetic

A toothpick expression represents a positive integer using toothpicks. It is made of operands and operators.

• An operand is one or more vertical toothpicks |. Its value equals the number of toothpicks it uses (for example, ||| has value 3).
• There are two operators, each built from exactly two toothpicks:
  • Addition is a plus sign + (one vertical toothpick and one horizontal toothpick).
  • Multiplication is the letter x (two toothpicks). Multiplication has higher precedence than addition.

An expression must start with an operand, then strictly alternate between operators and operands, and finish with an operand. For example, |||||||x||||| evaluates to $7 \times 5 = 35$ and uses $7 + 5 + 2 = 14$ toothpicks.

Given a positive integer $N$, consider every toothpick expression whose value equals $N$. Compute the smallest number of toothpicks any such expression can use.

The input consists of one or more lines. Each line contains a single positive integer $N$ with $1 \le N \le 5000$. Input ends at end of file.

For each integer $N$ in the input, print one line containing the minimum number of toothpicks needed to build a toothpick expression whose value is $N$.