問題文

正の整数 N が与えられます。N を 1 になるまで 2 以上の約数で割っていって数列を作ります。数列の各要素の各位の和の総和を最大化してください。

例えば、N=12 の場合、12,6,3,1 という数列を作ると 1+2+6+3+1=13 となり、これが最大です。

入力例1

12

出力例1

13

入力例2

1

出力例2

1

入力例3

100

出力例3

19