#P2182. [ABC099C] Strange Bank

[ABC099C] Strange Bank

题目描述

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

  • 11 日元
  • 66 日元,62(=36)6^2(= 36) 日元,63(=216)6^3(= 216) 日元,...
  • 99 日元,92(=81)9^2(= 81) 日元,93(=729)9^3(= 729) 日元,...

至少总共需要多少次操作才能确切提取 NN 日元?不允许重新存入您提取的钱。

输入格式

一个正整数 N(1N100000)N (1 \le N \le 100000)

输出格式

最少操作次数。

127
4
3
3
44852
16