問題文

整数の 9 には面白い性質があります。 どのような非負整数 N を選んでも N を 9 で割った余りと、 N を 10 進法で表記した時の各桁の数字の和を 9 で割った余りが一致するのです。

高橋君はこのような性質を持つ整数が他にないか気になりました。しかし、残念なことにこのような性質をもつ整数は 9 と 3 と 1 くらいしか見つかりませんでした。 そこで、「どのような非負整数 N を選んでも・・・」ではなくて「できるだけ多くの非負整数 N に対して・・・」というふうに性質の条件を落として探してみることにしてみました。

高橋君は非負整数 K がどれくらい多くの非負整数 N に対して上のような条件をみたすのかが知りたいです。

高橋君を手伝うために以下の問いに答えてください。

• 1 ≦ N ≦ M となる整数 N のうち K で割った余りと、N を 10 進法表記した時の各桁の数字の和を K で割った余りが一致するような N の個数を求めてください。

部分点

この問題には部分点が設定されている。

• 1 ≦ M ≦ 10^5 を満たすデータセットに正解した場合は 10 点が与えられる。
• 1 ≦ M ≦ 10^{10}を満たすデータセットに正解した場合はさらに 90 点が与えられる。合計で100点となる。

出力

問題文で挙げた条件に一致する非負整数の個数を 1 行で出力せよ。

入力例1

5 100

出力例1

19

1桁の整数はかならず条件を満たします。 そのほかに 50 ≦ N ≦ 59 を満たす整数は全て条件を満たします。 これら以外に条件を満たす整数は 100 以下の範囲にはありません。 よって 19 を出力します。

入力例2

112 32279

出力例2

309

入力例3

108 3141592653

出力例3

261799999

入力例4

9 10000000000

出力例4

10000000000