[ABC099C] Strange Bank

题面翻译

为了使取款变得困难，某家银行允许其客户在一次操作中仅取以下金额之一：

• $1$ 日元

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

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

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

不允许重新存入您提取的钱。

题目描述

ある銀行では、お金の引き出しを難しくするために、一回の操作で引き出せる金額が以下のいずれかとなっています。

• $1$ 円

• $6$ 円、$6^2(=36)$ 円、$6^3(=216)$ 円、$...$

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

この銀行からちょうど $N$ 円を引き出すには少なくとも何回の操作が必要か求めてください。

ただし、一度引き出したお金を再び預け入れてはならないとします。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$

输出格式

この銀行からちょうど $N$ 円を引き出すのに少なくとも $x$ 回の操作が必要な時、$x$ を出力せよ。

样例 #1

样例输入 #1

127

样例输出 #1

4

样例 #2

样例输入 #2

3

样例输出 #2

3

样例 #3

样例输入 #3

44852

样例输出 #3

16

提示

制約

• $1\ \leq\ N\ \leq\ 100000$

• $N$ は整数

Sample Explanation 1

$1$ 円、$9$ 円、$36(=6^2)$ 円、$81(=9^2)$ 円を引き出す操作をそれぞれ $1$ 回ずつ行うことで、合計 $4$ 回の操作で $127$ 円を引き出すことができます。

Sample Explanation 2

$1$ 円を 引き出す操作を $3$ 回 行うことで、合計 $3$ 回の操作で $3$ 円を引き出すことができます。