问题描述

为了使提款变得困难，某银行允许其客户在一次操作中只能提取以下金额中的一种:

• $1$ 元
• $6$ 元，$6^2(=36)$ 元，$6^3(=216)$ 元，
• $9$ 元，$9^2(=81)$ 元，$9^3(=729)$ 元，

至少需要多少次操作才能总共提取 $N$ 元？

你取的钱是不可以转存的。

数据规模

$1\leq N\leq 100000$

$N$ 是整数。

输入

输入由标准输入按以下格式给出:

$N$

输出

如果至少需要 $x$ 次操作才能提取总共正好 $N$ 元，则打印 $x$。

127

4

通过提取 $1$ 元、$9$ 元、$36(=6^2)$ 元和 $81(=9^2)$ 元，我们可以在四次操作中提取 $127$ 元。

3

3

通过三次提取 $1$ 元，我们可以分三次操作提取 $3$元。

44852

16