[ARC052D] 9

给定两个正整数 $K,M(1\le K,M\le 10^{10}$，需要求出有多少个 $\ge 1$ 且 $\le M$ 的 $N$，满足 $N$ 的各位之和和 $N$ 在模 $K$ 意义下同余。 对于 $10\%$ 的数据，满足 $1\le M\le 10^5$ 。

[problemUrl]: https://atcoder.jp/contests/arc052/tasks/arc052_d 整数の $ 9 $ には面白い性質があります。 どのような非負整数 $ N $ を選んでも $ N $ を $ 9 $ で割った余りと、 $ N $ を $ 10 $ 進法で表記した時の各桁の数字の和を $ 9 $ で割った余りが一致するのです。 高橋君はこのような性質を持つ整数が他にないか気になりました。しかし、残念なことにこのような性質をもつ整数は $ 9 $ と $ 3 $ と $ 1 $ くらいしか見つかりませんでした。 そこで、「どのような非負整数 $ N $ を選んでも・・・」ではなくて「できるだけ多くの非負整数 $ N $ に対して・・・」というふうに性質の条件を落として探してみることにしてみました。 高橋君は非負整数 $ K $ がどれくらい多くの非負整数 $ N $ に対して上のような条件をみたすのかが知りたいです。 高橋君を手伝うために以下の問いに答えてください。 - $ 1\ ≦\ N\ ≦\ M $ となる整数 $ N $ のうち $ K $ で割った余りと、$ N $ を $ 10 $ 進法表記した時の各桁の数字の和を $ K $ で割った余りが一致するような $ N $ の個数を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ K $ $ M $

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

5 100

19

112 32279

309

108 3141592653

261799999

9 10000000000

10000000000

### 制約 - 与えられる数字はすべて整数 - $ 1\ ≦\ K\ ≦\ M\ ≦\ 10^{10} $ ### 部分点 この問題には部分点が設定されている。 - $ 1\ ≦\ M\ ≦\ 10^5 $ を満たすデータセットに正解した場合は $ 10 $ 点が与えられる。 - $ 1\ ≦\ M\ ≦\ 10^{10} $を満たすデータセットに正解した場合はさらに $ 90 $ 点が与えられる。合計で$ 100 $点となる。 ### Sample Explanation 1 $ 1 $桁の整数はかならず条件を満たします。 そのほかに $ 50\ ≦\ N\ ≦\ 59 $ を満たす整数は全て条件を満たします。 これら以外に条件を満たす整数は $ 100 $ 以下の範囲にはありません。 よって $ 19 $ を出力します。