100992: [AtCoder]ABC099 C - Strange Bank

Problem Statement

To make it difficult to withdraw money, a certain bank allows its customers to withdraw only one of the following amounts in one operation:

• $1$ yen (the currency of Japan)

• $6$ yen, $6^2(=36)$ yen, $6^3(=216)$ yen, ...

• $9$ yen, $9^2(=81)$ yen, $9^3(=729)$ yen, ...

At least how many operations are required to withdraw exactly $N$ yen in total?

It is not allowed to re-deposit the money you withdrew.

Constraints

• $1 \leq N \leq 100000$
• $N$ is an integer.

Input

Input is given from Standard Input in the following format:

$N$

Output

If at least $x$ operations are required to withdraw exactly $N$ yen in total, print $x$.

Sample Input 1

127

Sample Output 1

4

By withdrawing $1$ yen, $9$ yen, $36(=6^2)$ yen and $81(=9^2)$ yen, we can withdraw $127$ yen in four operations.

Sample Input 2

3

Sample Output 2

3

By withdrawing $1$ yen three times, we can withdraw $3$ yen in three operations.

Sample Input 3

44852

Sample Output 3

16