题目描述

0 ～ 9 からなる文字列 $X$ と、整数 $M$ が与えられます。

$X$ に含まれる最も大きい数字を $d$ とします。

$d+1$ 以上の整数 $n$ を選んで $X$ を $n$ 進法表記の数とみなして得られる値のうち、$M$ 以下であるようなものは何種類あるでしょうか？

输入格式

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

$X$ $M$

输出格式

答えを出力せよ。

题目大意

给定一个由数字构成的字符串 $X$ 和一个整数 $M$。定义 $d$ 为 $X$ 中最大的数字。

求 $n$ 的个数，满足 $n>d$ 且将 $X$ 视为一个 $n$ 进制数 $X^\prime$ 时，$X^\prime\le M$。

22
10

2

999
1500

3

100000000000000000000000000000000000000000000000000000000000
1000000000000000000

1

提示

制約

• $X$ は 0 ～ 9 のみからなる
• $X$ の長さは $1$ 以上 $60$ 以下
• $X$ の先頭の文字は 0 ではない
• $1\ \leq\ M\ \leq\ 10^{18}$

Sample Explanation 1

$X$ に含まれる最も大きい数字は 2 です。 - $X$ を $3$ 進法表記とみなして得られる値は $8$ です。 - $X$ を $4$ 進法表記とみなして得られる値は $10$ です。 得られる値のうち $10$ 以下のものはこの $2$ つのみです。

Sample Explanation 2

$X$ に含まれる最も大きい数字は 9 です。 - $X$ を $10$ 進法表記とみなして得られる値は $999$ です。 - $X$ を $11$ 進法表記とみなして得られる値は $1197$ です。 - $X$ を $12$ 進法表記とみなして得られる値は $1413$ です。 得られる値のうち $1500$ 以下のものはこの $3$ つのみです。

Sample Explanation 3

$X$ を $2$ 進法表記とみなして得られる $576460752303423488$ が、唯一の $1000000000000000000$ 以下の得られる数です。