题面

某银行为增加取款难度，规定每次取款只能选取以下特定金额之一：

• 1 哈夫币
• 6 的幂次（( 6^1 = 6 )、( 6^2 = 36 )、( 6^3 = 216 ) … ）
• 9 的幂次（( 9^1 = 9 )、( 9^2 = 81 )、( 9^3 = 729 ) … ）

现在需要计算，要提取恰好 ( N ) 哈夫币，至少需要多少次取款操作（每次操作取一种允许的金额，取出的钱不能重新存入再取 ）。

输入描述

输入一个整数 ( N ) ，表示要提取的哈夫币总数，满足 ( 1 \leq N \leq 100000 ) 且 ( N ) 为整数。

输出描述

输出一个整数 ( x ) ，表示提取 ( N ) 哈夫币所需的最少操作次数。

样例输入 1

127

样例输出 1

4

样例解释 1

提取 127 哈夫币的最优方案是：分别进行 1 次取 1 哈夫币、1 次取 9 哈夫币、1 次取 36（( 6^2 ) ）哈夫币、1 次取 81（( 9^2 ) ）哈夫币的操作，总共 4 次操作，可凑出 127 哈夫币（( 1 + 9 + 36 + 81 = 127 ) ）。

样例输入 2

3

样例输出 2

3

样例解释 2

由于只能取 1 哈夫币，要提取 3 哈夫币需要进行 3 次取 1 哈夫币的操作，所以最少操作次数是 3 。

样例输入 3

44852

样例输出 3

16

样例解释 3

通过合理选择 1 哈夫币、6 的幂次哈夫币、9 的幂次哈夫币的组合，最少需要 16 次操作可提取出 44852 哈夫币。