题目描述

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.

某银行为了增加取款的难度，只允许客户在一次操作中提取下列金额之一：

• $1$ 日元（日本货币）

• $6$ 日元， $6^2(=36)$ 日元， $6^3(=216)$ 日元，...

• $9$ 日元、 $9^2(=81)$ 日元、 $9^3(=729)$ 日元、...

至少需要进行多少次操作才能取出 $N$ 日元？

取出的钱不能再存入银行。

输入格式

输入内容按以下格式标准输入：

$N$

输出格式

如果至少需要进行 $x$ 次操作才能准确提取 $N$ 日元，则打印 $x$ 。

样例 #1

样例输入 #1

127

样例输出 #1

4

样例 #2

样例输入 #2

3

样例输出 #2

3

样例 #3

样例输入 #3

44852

样例输出 #3

16

说明

数据规模与约定

• $1 \leq N \leq 100000$
• $N$ 是整数。

样例 $1$ 解释

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

样例 $2$ 解释

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