第19回日本情報オリンピック　二次予選

2019年12月12日
情報オリンピック日本委員会

問題文

JOI 君は初めに 1 以上 N 以下のある整数を持っていた．JOI 君は以下の操作を 0 回以上行ったところ，持っている整数が N になった．

• 持っている整数を十進法で表したときの各桁の和を，持っている整数に足す．

N が与えられるので，JOI 君が初めに持っていた可能性のある整数の個数を求めるプログラムを作成せよ．

制約

• 1 ≦ N ≦ 1 000 000．
• N は整数である．

入力

入力は以下の形式で標準入力から与えられる．
N

出力

JOI 君が初めに持っていた可能性のある整数の個数を 1 行で出力せよ．

入出力例

入力例 1
13

出力例 1
4

• 例えば JOI 君が初めに整数 5 を持っており，3 回操作を行った場合 5 → 10 → 11 → 13 と変化する．JOI 君が初めに持っていた可能性のある整数は 5,10,11,13 の 4 個のみである．

入力例 2
20

出力例 2
1

入力例 3
2019

出力例 3
449