Problem G
Organ-free Man
Every so often, a shipment of universal robots comes from Earth to Mars in order to help you with routine colonization tasks. The robots are called Organ-free Men (precisely OFMv5001.41.912) and each one of them is identified by a unique serial number, which is a positive integer.
To prevent space theft, OFMs are transported from Earth to Mars in a locked state and have to be first unlocked by a special password. The password to unlock an OFM is based on its serial number and a function $f(x)$. The function $f(x)$ is defined as follows.
If $0 \le x \le 9$, then $f(x) = x!$, and if $x > 9$, then $f(x) = (x \mod 10)! + f(\lfloor x/10 \rfloor $). The brackets $\lfloor \rfloor $ denote the floor value of a number (e.g. $\lfloor 2.43 \rfloor = 2$). Exclamation mark denotes the factorial, i.e., $x! = 1 \cdot 2 \cdot \cdots \cdot x$ for $x > 0$ and $0! = 1$.
To unlock an OFM with a serial number $y$, you need to input smallest such non-negative integer $x$, so that $f(x) = y$ holds.
Will you manage to unlock all robots that were shipped to you?
Input
The input consists of one integer $y$ ($1 \le y \le 10^9$), the serial number of a particular OFM.
Output
Output a single non-negative integer $x$, the password to unlock the particular OFM.
| Sample Input 1 | Sample Output 1 |
|---|---|
3 |
12 |
| Sample Input 2 | Sample Output 2 |
|---|---|
20 |
2333 |