Given a positive integer N (0<=N<=10000), you are to find an expression equals to N using only 1,+,*,(,). 1 should not appear continuously, i.e. 11+1 is not allowed.
Input
There are multiple test cases. Each case contains only one line containing a integer N
Output
For each case, output the minimal number of 1s you need to get N.