To make it difficult to withdraw money, a bank on the planet Krokrys only allows its customers to withdraw one of the following amounts per transaction:
- 1 kroratcoin (a valid coin on the planet Krorat);
- 6 Croratscoins, 36 (=6
2) Croratscoins, 216(=6
3) Croratscoins , ...;
- 9 Croratscoins, 81 (=9
2) Croratscoins, 729(=9
3) Croratscoins , ...
What is the minimum number of operations required to output exactly
N kroratcoins?
It is not possible to re-deposit the money you have withdrawn.
Input
The input is an integer
N (
\(1<=N<=100000\)).
Imprint
Output the answer to the problem.
Examples
| # |
Input |
Output |
Explanations |
| 1 |
127 |
4 |
If you withdraw 1 + 9 + 36 + 81, you will withdraw 127 kroratcoins in 4 operations. |
| 2 |
3 |
3 |
1+1+1 = 3, total 3 operations |
| 3 |
44852 |
16 |
|