小T偶然间发现了一些魔法数字，这些数字可以转换为任意数的阶乘，如1、2、6、24...。小T想知道，对于某一个整数，至少需要多少个魔法数字组成呢？

多样例测试，以读到文件末尾作为结束，样例数不超过100000。
每行输入一个整数N，0<=N<=1e18。

对于每行输入，输出至少需要多少个魔法数字组成，单独占一行。

6 = 3！
8 = 2！+3！
23 = 1! + 2! x 2 + 3！x 3