题目描述

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

• 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$。

示例输入1

127

示例输出1

4

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

示例输入2

3

示例输出2

3

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

示例输入3

44852

示例输出3

16